A graph $$G$$ is isomorphic to the line graph $$L(G)$$ if and only if $$G$$ is the disjoint union of cycles.

Proof:

1. If $$G$$ has a connected component with two or more cycles in it, $$L(G)$$ has a corresponding component with a greater number of vertices and two or more cycles. Therefore, in this case, repeating the line graph construction from $$G$$ must eventually lead to arbitrarily large graphs, so $$L(G)$$ cannot be isomorphic to $$G$$.

2. If $$G$$ does not have a component with two cycles, it is a pseudoforest. If some component of this pseudoforest has both a cycle and some edges not in the cycle, then the corresponding component of $$L(G)$$ has at least two cycles (one for the cycle itself and one for where the other edges meet the cycle). Therefore, again, repeated line graphs grow arbitrarily large and $$L(G)$$ cannot be isomorphic to $$G$$.

3. In the remaining case, $$G$$ is a union of disjoint cycles and trees. If any component of $$G$$ is a tree, $$L(G)$$ would have fewer vertices than $$G$$. So, if $$L(G)$$ is isomorphic to $$G$$, each component of $$G$$ must be a cycle.

atheorist:
2006-11-02T02:39:36Z

I think you are talking about finite graphs (which is fine).

If you were talking about infinite graphs, then the graph of the predecessor/successor relation on the integers would be isomorphic to its line graph.

If you were talking about an embedded graph, you could define a different L, where nodes become cycles instead of cliques. Your proof would still hold for finite graphs and the graph of the predecessor/successor relation. However, the infinite grid graph would be isomorphic to its L.

11011110:
2006-11-02T03:41:30Z

Yeah, I was only thinking about finite graphs.

If you were talking about infinite graphs, then the graph of the predecessor/successor relation on the integers would be isomorphic to its line graph.

It's tempting to think of that as being the infinite cyclic graph, analogously to Z being the infinite cyclic group. But a similar graph on the nonnegative integers is also isomorphic to its line graph, and nonisomorphic to your example.

If you were talking about an embedded graph, you could define a different L, where nodes become cycles instead of cliques. Your proof would still hold for finite graphs and the graph of the predecessor/successor relation. However, the infinite grid graph would be isomorphic to its L.

You mean the medial graph, I think. Interesting example with the grid, since the isomorphism involves a surprising 45 degree rotation and sqrt(2) scaling.

None:
2006-11-23T16:41:46Z

I think that this theorem is stated and proved in Harary's Graph Theory Book, 1969 - chapter on line graphs.

11011110:
2006-11-23T16:52:16Z

Thanks. I don't have his book to check, but there's also something similar to it on the MathWorld line graph page.

None: Here is the online reference
2007-02-08T01:43:14Z

Please look at page 72