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 $G$ es un gráfico lineal, entonces para cualquier vértice $v$ de $G$ los vecinos de $v$ puede dividirse en a lo sumo dos conjuntos de vértices tales que el subgrafo de $G$ inducido por cada conjunto de vértices es una camarilla.
Quiero preguntar si esta condición necesaria es suficiente para $G$ siendo una línea gragh. Si no es así, por favor da un contraejemplo.
