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

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|cite|improve this question
Thank you all. I up voted all answers. – Amr Nov 14 '12 at 20:41
up vote 6 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|cite|improve this answer

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|cite|improve this answer

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

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

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.