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

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.