Show and prove that the petersen graph is hypohamiltonianSol

Show and prove that the petersen graph is hypohamiltonian.

Solution

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. Thus peterson graph is non hamiltonian.