Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|improve this answer
    
Thanks, for your answer. –  Andrés Felipe Téllez Crespo Jan 28 '13 at 18:22

Your Answer

 
discard

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.