Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems

Found at Wolfram:

The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a $10-$cycle $C$, then the graph consists of $C$ plus five chords. If each chord joins vertices opposite on $C$, then there is a $4-$cycle. Hence some chord $e$ joins vertices at distance $4$ along $C$. Now no chord incident to a vertex opposite an endpoint of $e$ on $C$ can be added without creating a cycle with at most four vertices. Therefore, the Petersen graph is non-Hamiltonian.

There is a different simple proof here.


Here is a proof I like. The Petersen graph has $10$ vertices. If you have a Hamilton Cycle, it must go through each vertex. So then you draw this Hamilton cycle (just your basic cycle with $10$ vertices and $10$ edges). Now, Petersen graph has $15$ edges, so you have to add $5$ more edges to your cycle. However, any way you do this must create a $3$ or $4$ cycle, of which the graph has none. You can verify this last part for yourself and it is a simple combinatorial argument.

This type of proof is often quite effective for showing the lack of a Hamilton cycle.

Tags:

Graph Theory