Every gragh below will refer to a finite simple graph.

There is a necessary and sufficient condition for a nonempty gragh being a line gragh:

Krausz's Theorem

A nonempty gragh is a line gragh if and only if its edge set can be partitioned into a set of cliques with the property that any vertex lies in at most two cliques.

And we can find an obvious necessary condition for a nonempty gragh being a line gragh:

If a nonempty gragh $G$ is a line graph,then for any vertex $v$ of $G$,the neighbours of $v$ can be partitioned into at most two vertex sets such that the subgragh of $G$ induced by each vertex set is a clique.

I want to ask if this necessary condition is sufficient for $G$ being a line gragh.If not,please give a counterexample.


1 Answer 1


No. The graphs you define are called "quasi-line graphs" and are a larger class than line graphs. If you search for "quasi-line graph" you will find a lot of literature on them.

The simplest counterexample is $K_{1,3}$. A larger one is a graph consisting of two copies of $K_4$ sharing one edge.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.