Grafo línea

En teoría de grafos, el grafo línea, de línea, lineal o representativo[1]​ L(G) de un grafo no dirigido G es un grafo que representa las adyacencias entre las aristas de G. Su nombre se debe a un artículo de Harary y Norman (1960), aunque tanto Whitney (1932) como Krausz (1943) los definieron antes.En otras palabras, con una única excepción, un grafo conexo siempre puede ser obtenido si conocemos las adyacencias de sus aristas (líneas).La siguiente figura muestra un grafo (a la izquierda, con vértices azules) y su grafo línea (derecha, con vértices verdes).Cada vértice del grafo línea está etiquetado con el par de nodos finales de la correspondiente arista en el grafo original.El vértice verde 1,3 es adyacente a otros tres vértices verdes: 1,4 y 1,2 (correspondientes a aristas que comparten el nodo final 1 en el grafo azul) y 4,3 (correspondiente a una arista compartiendo el nodo final 3 en el grafo azul).