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.

How to prove Petersen graph has no Hamiltonian cycle?

Drawings of the Petersen graph

My working

$step \ 1.$ first assume that there exists a cycle.

$step \ 2.$ now take a-b-c three continuous node from cycle,than delete node b and add an edge between a and c.

$step \ 3$ from step 2 we are reducing 2 edges and 1 vertex from previous graph.

$step \ 4$ finally when we have deleted all 10 nodes means we have deleted 20 edges, but we have only 15 edges that means contradiction to our assumption.

share|improve this question
    
This question has been asked here and here. (I don't think this is a duplicate since you're asking about your particular approach.) Nice drawings, by the way. –  Douglas S. Stones Apr 19 '13 at 12:33
    
I don't think your Step 3 reasoning is valid. In order for it to be true, you need $b$ to have degree 3 (if it has degree 2, you're only removing 1 vertex and 1 edge by deleting it). This is fine the first time through, but once you start removing edges from your graph I see no way to guarantee that you'll still have a vertex of degree 3 left to delete... –  Micah Apr 19 '13 at 12:54

1 Answer 1

There are $10$-vertex $15$-edge (and $3$-regular) graphs that are Hamiltonian. For example:

A Hamiltonian $10$-vertex $15$-edge graph

This essentially means that no proof can exist that only accounts for number of vertices and edges (or the degree sequence), since there are both Hamiltonian and non-Hamiltonian examples. Any proof must be able to separate the Petersen graph from the graph above. We also cannot expect to find a simple algorithm, since the problem is NP-complete.

There are some bugs in the argument: along with what Micah mentioned, there are instances where there aren't three vertices $a$, $b$ and $c$.

share|improve this answer

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.