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

Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. Thanks!

-
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work. – André Nicolas Feb 3 '13 at 5:16
– Gerry Myerson Feb 3 '13 at 11:24

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.

-
I never covered chords in class. – DJ_ Feb 3 '13 at 19:12
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture. – Gerry Myerson Feb 3 '13 at 23:16

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.

-