# How to prove Petersen graph has no Hamiltonian cycle?

How to prove Petersen graph has no Hamiltonian cycle?

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.

-
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

There are $10$-vertex $15$-edge (and $3$-regular) graphs that are Hamiltonian. For example:
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$.