Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work. –  André Nicolas Feb 3 '13 at 5:16
    
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.