2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Apr 3 '13 at 1:37
  • $\begingroup$ 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. $\endgroup$ – user41419 Apr 3 '13 at 1:57
  • $\begingroup$ What is $\nu_G$? Explaining your notation (even if it is sort of standard) never hurts. $\endgroup$ – Mariano Suárez-Álvarez Apr 3 '13 at 2:03
  • $\begingroup$ $v_G$ is the number of vertices of $G$. I have edited my post to add this explanation! $\endgroup$ – user41419 Apr 3 '13 at 2:04
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user41419 Apr 3 '13 at 5:51
  • $\begingroup$ @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! $\endgroup$ – Henning Makholm Apr 3 '13 at 11:31
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy