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