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.

It is easy to show that all connected $2$-regular graphs are Hamiltonian. The Petersen graph is a $3$-regular graph that is not Hamiltonian. Are there any $4$ regular graphs that are not Hamiltonian?

Thank you

share|improve this question
1  
Thank you all. I up voted all answers. –  Amr Nov 14 '12 at 20:41
add comment

3 Answers

up vote 4 down vote accepted

Note that you didn't specify connected graph, which is certainly necessary for Hamiltonicity. More generally, a Hamilton cycle has the property that deleting any $k$ vertices breaks the cycle into at most $k$ connected components. In the case $k=1$ a Hamiltonian graph must be strongly connected.

Pick your favourite $4$-regular graph $G$, and delete one edge $e$ so it has two vertices of degree $3$. Take two copies of $G-e$, and create a new vertex that is adjacent to the four deficient vertices. The resulting graph is $4$-regular, connected, but not strongly connected.

Also, did you try Googling 4-regular non-Hamiltonian? The Meredith graph is very strongly connected, $4$-regular and still not Hamiltonian.

share|improve this answer
add comment

The answer is no. The graph on the picture is the smallest counterexampleenter image description here

You can most likely generalize this construction for every $k > 4$ and deduce that you can always find connected $k$-regular graphs that are not Hamiltonian.

share|improve this answer
add comment

However, Tutte proved that a 4-connected planar graph is Hamiltonian.

share|improve this answer
    
Thanks for this piece of information –  Amr Sep 18 '13 at 17:02
add comment

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.