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

Suppose you are given a graph $G$ with the properties that $G$ is 3-regular, $v_G = 10$ where $v_G$ is the number of vertices in $G$, and girth$(G) \geq 5$. How can you tell that $G$ is not Hamiltonian?

So far, I have been trying to figure it out by looking at the Petersen graph, which I know is not Hamiltonian via a result in a book I have. The Petersen graph has $v_G = 10$ and girth$(G) = 5$, but I don't know how this relates to being non-Hamiltonian.

share|cite|improve this question
It's not true for all graphs satisfying these conditions. For example, a 5-cycle fused with a 7-cycle such that they share two neighbor nodes will have 10 vertices and girth 5, but still be nicely Hamiltonian. – Henning Makholm Apr 3 '13 at 1:37
Oops, upon reading my post again I realize I forgot to add the property that $G$ was 3-regular. My bad! But nice counterexample for the original post. – user41419 Apr 3 '13 at 1:57
What is $\nu_G$? Explaining your notation (even if it is sort of standard) never hurts. – Mariano Suárez-Alvarez Apr 3 '13 at 2:03
$v_G$ is the number of vertices of $G$. I have edited my post to add this explanation! – user41419 Apr 3 '13 at 2:04
up vote 3 down vote accepted

It looks like the only 3-regular graph with exactly 10 vertices and girth $\ge 5$ is the Petersen graph. So the fact that all such graphs are non-Hamiltonian is simply because the Petersen graph happens to be.

First suppose the girth is 5 exactly: Start by drawing the 5-cycle. Because the graph is 3-regular, each of the vertices in the 5-cycle must have an additional neighbor, and these neighbors must all be new and distinct because otherwise the girth requirement would be violated. But that means that we now know all of the vertices, and the only way we can give each of the new vertices two more edges without creating 4-cycles is to connect them exactly as the Petersen graph.

If the girth is 6 or more, a similar argument quickly produces a contradiction.

share|cite|improve this answer
Thank you very much for the clear answer! I am curious. Does a proof exist that does not require referencing the Petersen graph? (Even if it is the only graph satisfying such requirements) That is, is there some general criteria that would force a graph to be non-Hamiltonian based solely on the number of vertices/girth/regularness? – user41419 Apr 3 '13 at 5:51
@user41419: I have trouble imagining there could be any such criteria, except to the extent they force the graph to be one of a few particular graphs, as in this case. So it's a trick question! – Henning Makholm Apr 3 '13 at 11:31

I know of a theorem that states "Let $G$ be a graph. If there is a set $S$ of vertices such that $G-S$ has more than $|S|$ components, then $G$ has no Hamiltonian cycle." It can be proved by contradiction.

I'm assuming that by 'Hamiltonian' you mean 'Hamiltonian Cycle', as that's what we learned in school. Also, a component is a set of vertices with no neighbors outside of the set.

share|cite|improve this answer

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.