Todos los grafos que aparecen a continuación se refieren a un grafo simple finito.
Existe una condición necesaria y suficiente para que un gragh no vacío sea un gragh de línea:
Teorema de Krausz
Un gragh no vacío es un gragh de línea si y sólo si su conjunto de aristas puede dividirse en un conjunto de cliques con la propiedad de que cualquier vértice se encuentra como máximo en dos cliques.
Y podemos encontrar una condición necesaria obvia para que un gragh no vacío sea un gragh de línea:
Si un gragh no vacío GG es un gráfico lineal, entonces para cualquier vértice vv de GG los vecinos de vv puede dividirse en a lo sumo dos conjuntos de vértices tales que el subgrafo de GG inducido por cada conjunto de vértices es una camarilla.
Quiero preguntar si esta condición necesaria es suficiente para GG siendo una línea gragh. Si no es así, por favor da un contraejemplo.