# 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

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

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