How many graphs can have the same line graph?

494 Views Asked by At

Suppose we have a finite simple graph $G$. Call $\mathcal O$ the set of graphs without isolated vertices up to isomorphism whose line graph is isomorphic to $G$. Can $\mathcal O$ contain more than one element?

1

There are 1 best solutions below

1
On BEST ANSWER

According to Wikipedia, "Hassler Whitney (1932) proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph." The reference is given as Whitney, H. (1932), "Congruent graphs and the connectivity of graphs", American Journal of Mathematics 54 (1): 150–168, doi:10.2307/2371086, JSTOR 2371086.

There is also a reference to Harary, F. (1972), "8. Line Graphs", Graph Theory, Massachusetts: Addison-Wesley, pp. 71–83; it says, "Harary gives a simplified proof of this theorem by Jung."

Whitney's result is given as, "If the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph $K_3$ and the claw $K_{1,3}$, which have isomorphic line graphs but are not themselves isomorphic."