0
$\begingroup$

If $G = (V,E)$ is a finite, connected, simple, undirected graph, is there a Hamiltonian path in the line graph $L(G)$ of $G$?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.