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.