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!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.