Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.]
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.
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.
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.
