Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
MathOverflow

Return to Answer

Post Undeleted by 1001
added 25 characters in body
Source Link
1001
1001
  • 991
  • 4
  • 8

No, not necessarily. Hamiltonian paths in the line graph $L(G)$ correspond to Eulerian walks inConsider the original graph $G$. By Euler's theorem, a connected 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 an Eulerian walk if and only if all but at most 2three vertices of $G$ have even degree 1. Therefore $L(G)$ has no Hamiltonian path.

No, not necessarily. Hamiltonian paths in the line graph $L(G)$ correspond to Eulerian walks in the original graph $G$. By Euler's theorem, a connected graph has an Eulerian walk if and only if all but at most 2 vertices of $G$ have even degree.

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.

Post Deleted by 1001
Source Link
1001
1001
  • 991
  • 4
  • 8

No, not necessarily. Hamiltonian paths in the line graph $L(G)$ correspond to Eulerian walks in the original graph $G$. By Euler's theorem, a connected graph has an Eulerian walk if and only if all but at most 2 vertices of $G$ have even degree.