If $G = (V,E)$ is a finite, connected, simple, undirected graph, is there a Hamiltonian path in the line graph $L(G)$ of $G$?
$\begingroup$ 
$\endgroup$
asked Apr 15, 2023 at 10:51
Dominic van der Zypen
53.7k9 gold badges53 silver badges193 bronze badges
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
No. Consider the graph $G = (V, E)$ with $$V = \{0,1,2,3,4,5,6\}\quad \text{and} \quad E = \{\{0,1\}, \{1, 2\}, \{0,3\}, \{3, 4\}, \{0,5\}, \{5, 6\}\}.$$ Note that its line-graph has three vertices of degree 1. Therefore $L(G)$ has no Hamiltonian path.
