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

It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either.

Is there a simple (short) argument that the Petersen Graph does not contain a Hamiltonian cycle?

share|cite|improve this question
The case distinction can be reduced immensely if you are allowed to use the fact that the Petersen graph is 3-arc-transitive. – Jernej Jan 7 '13 at 16:04
how can we show it is 3 arc transitive. I proved it is enough to show it has one orbit on 3-arcs. But I am not good at combinatorics arguments so I would love a hint. – H_B Feb 24 at 18:41
up vote 8 down vote accepted

If you can use the symmetry (as Jernej suggests), the case argument has a lot going for it.

There is a proof using interlacing. Observe that if $P$ has a Hamilton cycle then its line graph $L(P)$ contains an induced copy of $C_{10}$. Eigenvalue interlacing then implies that $\theta_r(C_{10}) \le \theta_r(L(P))$. But $\theta_7(C_{10}) \approx -0.618$ and $\theta_7(L(P))=-1$. [I have forgotten who this argument is due to. There are a number of variants of it too.]

share|cite|improve this answer

Assume there exists a Ham. cycle. Color the vertices along the cycle alternately $5$ Red and $5$ Blue. Each vertex now has at least two neighbors of the opposite color.

But starting with two adjacent vertices of the same color (must exist on a non-bipartite graph), there is only one way to complete a $2$-coloring, with at least two neighbors of the opposite color to every vertex. It turns out that $6$ vertices get one color and $4$ get the other -a contradiction.

share|cite|improve this answer

Another easy argument is by using the edge chromatic number which is 4 for the Petersen graph.If it Hamiltonian, then removing the Hamiltonian cycle leaves a perfect matching. In this case 3 colors would be sufficient for edge coloring: 2 for the cycle and 1 for the matching.

share|cite|improve this answer

Motivated from the wikipedia page I will add an answer to the question by myself. It is still a little case distinction, but it is small.

We know that the Petersen graph is 3-regular and has girth 5. Suppose it has a Hamiltonian cycle $H$ and we draw the graph such that the $H$ is drawn as cycle. The edges that are not in $H$ are chords of $H$. If there would be two chords that do not intersect, then these two chords are part of two disjoint 5 cycles. But in this case the two chords and the two edges of $H$ not in the 5-cycles form a 4-cycle. Hence all chords cross pairwise. The only possibility for this is shown in the second picture. Clearly, we have a 4-cycle. Hence, we have a contradiction.

enter image description here

share|cite|improve this answer

if it had a hamiltonian circle we will find a complete matching... so if we check all 6 matching of petersen graph we can see after removing a complete matching from petersen the second graph isn't one circle. this is proving that petersen graph dosn't have a hamiltonian circle.

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.