[Math] If the graph $G$ has an Eulerian circuit, prove that its line graph has a Hamiltonian cycle

graph theory

Let G be a simple, undirected graph. Construct another graph G' as follows —
for each edge e in G, there is a corresponding vertex ve in G'
, and for any two vertices ve and ve
'
in G'
, there is a corresponding edge {ve, ve
'} in G'
if the edges e and e
'
in G are incident on the
same vertex. We conjectures that if G has an Eulerian circuit, then G' has a Hamiltonian
cycle. Prove or disprove this conjecture. You may assume that G has at least one edge.

I'm struggling to understand what this G' would even look like.
Thanks

Best Answer

Consider the Eulerian circuit in $G$ that passes through edges that we can label $e_1, e_2, \ldots, e_m$, with both $e_1$ and $e_m$ incident on vertex $v_r$. Note that by definition we do not revisit any edge.

Then a Hamiltonian cycle in $G'$ can be found through vertices $v_{e_1},v_{e_2},\ldots,v_{e_m}$ since these vertices are joined by edges, by virtue of the corresponding vertices in $G$ that successive edges in the Eulerian circuit are incident upon.

Related Question