A graph equation between the line graph and the edge-complement graph

Resumen

A partir de un grafo $G$ se pueden construir grafos relacionados, como su grafo de líneas $L(G)$ y su grafo complemento de aristas $\overline{G}$. Después de mostrar cómo las propiedades de $G$ implican propiedades de $L(G)$, nos preguntamos cuán diferentes son los conceptos del grafo lineal $L(G)$ y el del grafo complemento de aristas $\overline{G}$, resolviendo la ecuación $L(G) \simeq \overline{G}$. Demostramos que la ecuación tiene solo dos soluciones. La prueba utiliza un argumento sobre el grado de los vértices de un grafo que permite reducir el número de posibles soluciones hasta poder comprobarlas algorítmicamente. Esto da una prueba alternativa a la de Aigner.