Useless graph theory result #421965
A graph \( G \) is isomorphic to the line graph \( L(G) \) if and only if \( G \) is the disjoint union of cycles.
Proof:
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 \).
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 \).
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.
Comments:
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.
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.
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.
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.