# Any graph from the Petersen graph has a hamiltonian cycle if one edge is added

Prove that any graph that can be obtained from the Petersen graph by adding one extra edge has a Hamiltonian cycle.

So I've found that removing any vertex yields a Hamiltonian cycle -- I'm not sure if that's relevant or helpful, as I wasn't able to link that to the main question above. I thought I'd include that in case though.

• What have you tried and where are you stuck? Providing context such as this when asking a question better enables users to tailor their answers/hints to an appropriate and ultimately more useful level. As well, most users object to doing homework for others; you must demonstrate some effort first. – Ben Sheller Mar 8 '16 at 5:53
• Sure, thanks for the tip. I added some of what I understood and discovered so far to the original question, as you suggested. – Student Mar 8 '16 at 6:36
• How about proving that if $u,v$ are vertices in the Peterson graph, there is a Hamiltonian path from $u$ to $v$? – Christopher Carl Heckman Mar 8 '16 at 6:55