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