Let $G=(V,E)$ be a graph that can be partitioned into Hamiltonian cycles. Show that there is a Eulerian cycle in $G$.

My intuition: I need help with the proof (I'm not sure my intuition is right) taking the union of all the subsets gives us a Hamiltonian cycle in $G$ Hamiltonian cycle has no repetitions when it comes to vertices then if there are no repetitions it means that there is no repetition when it comes to the edges either which means there has to be a Eulerian cycle by defintion.

Thanks in advance

  • $\begingroup$ Your intution is fine. You just need to formalise it now. The essence is to go around all the Hamiltonian cycles one after another to form an Eulerian cycle. $\endgroup$ – Donald Splutterwit Mar 18 '17 at 11:54
  • $\begingroup$ @DonaldSplutterwit or, because of the even degree conferred by the Hamiltonian cycles, my answer using them. $\endgroup$ – Parcly Taxel Mar 18 '17 at 12:01

For a given Hamiltonian cycle, every vertex is incident to two edges in it. Since the graph can be partitioned into such cycles, every vertex must have the same even degree, and so it must have an Eulerian cycle. (The other condition for an Eulerian cycle, connectedness, is satisfied because there is a Hamiltonian cycle.)

  • $\begingroup$ I still don't understand why the even degree means that there must be an eulerian cycle. Thanks for your answer and edt! $\endgroup$ – user21312 Mar 18 '17 at 12:10
  • $\begingroup$ @user21312 Essentially you just stitch the Hamiltonian cycles that are given as partitioning $G$ together so you get one cycle. The stitching can be done at any vertex. $\endgroup$ – Parcly Taxel Mar 18 '17 at 12:15
  • 1
    $\begingroup$ False. You're missing the connectedness criterion. $\endgroup$ – John Dvorak Mar 18 '17 at 15:59
  • $\begingroup$ @JanDvorak Except that a Hamiltonian cycle in a graph implies it is connected... $\endgroup$ – Parcly Taxel Mar 18 '17 at 16:00

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.