Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Show that every Hamiltonian 3-regular graph has at least three Hamiltonian cycles.

I think that I could use the result that says that every graph with odd vertex degree every edege lies on a even number of Hamiltonian cycles.

share|cite|improve this question
up vote 3 down vote accepted

By hypothesis, you have a Hamiltonian cycle $H_1$. Choose any edge $e$ of $H_1$. Since it must lie on an even number of Hamiltonian cycles, you must have at least one more Hamiltonian cycle $H_2$. Now, $E(H_1) \setminus E(H_2) \neq \emptyset$, since otherwise $H_1$ and $H_2$ are identical. We know also that $e \notin E(H_1) \setminus E(H_2)$, since it is in both cycles. In other words, there is another edge $f \neq e$ lying on $H_1$ but not $H_2$. Since $f$ must lie on an even number of Hamiltonian cycles, there must be a third Hamiltonian cycle.

share|cite|improve this answer
Thanks, for your answer. – Andrés Felipe Téllez Crespo Jan 28 '13 at 18:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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