1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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? $\endgroup$ – JMoravitz Nov 14 '17 at 5:09
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joffan Nov 16 '17 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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