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

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

• $G'$ is a Line Graph of the original graph. Visit the link for examples and further description. As for the content of the assignment, consider the fact that $G$ has an eulerian circuit that goes through the edges of $G$ in a specific order. How might a circuit in $G$ going through a sequence of edges correspond to something in $G'$? Would the circuit taken in $G$ correspond to a circuit in $G'$? What properties might the circuit in $G'$ have? – JMoravitz Nov 14 '17 at 5:09

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

• The converse is not true, of course. This can be demonstrated by connecting an extra vertex to each vertex of a triangle ($K_3$) for $G$; $G'$ still has a Hamiltonian cycle even though $G$ doesn't even have an Eulerian path. – Joffan Nov 16 '17 at 20:59