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
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.
