# How to show a graph is not Hamiltonian?

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.

• 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-Álvarez 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

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.
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.