# Useless graph theory result #421965

A graph

Proof:

(1) If

(2) If

(3) In the remaining case,

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.

Yeah, I was only thinking about finite graphs.

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

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

Please look at page 72 http://books.google.com/books?hl=en&dq=Graph+Theory&vid=ISBN0201410338&id=9nOljWrLzAAC&lpg=PP1&pg=PP1&ots=9-ohrFrqWe&sig=2cSmSelAKxfLmsD-7C3DpVhVbew#PPA72,M1

*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.### Comments:

**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 http://books.google.com/books?hl=en&dq=Graph+Theory&vid=ISBN0201410338&id=9nOljWrLzAAC&lpg=PP1&pg=PP1&ots=9-ohrFrqWe&sig=2cSmSelAKxfLmsD-7C3DpVhVbew#PPA72,M1