# Short proof for the non-Hamiltonicity of the Petersen Graph

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?

-
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

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

-

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.

-

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.

-

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.

-

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.

-