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!
 A: 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.
A: 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. 
