Is the line graph of a Hamilton-connected graph is also Hamilton-connected?

102 Views Asked by At

If a graph G is Hamilton-connected, is it true that its line graph must also be Hamilton-connected? If yes, how to show it, and if no, what would be the counter example?

We know that converse of this statement is not true. I mean the line graph of the Petersen graph is Hamilton-connected, but Petersen graph itself is not Hamilton-connected.

1

There are 1 best solutions below

1
On

If the line graph is Hamilton-connected, then it is also Hamiltonian. This means that the original graph is Eulerian. The complete graph $K_4$ is Hamilton-connected, but not Eulerian (too many vertices of odd degree).