# 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