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.

  • $\begingroup$ 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. $\endgroup$ – Ben Sheller Mar 8 '16 at 5:53
  • 1
    $\begingroup$ Sure, thanks for the tip. I added some of what I understood and discovered so far to the original question, as you suggested. $\endgroup$ – Student Mar 8 '16 at 6:36
  • 1
    $\begingroup$ How about proving that if $u,v$ are vertices in the Peterson graph, there is a Hamiltonian path from $u$ to $v$? $\endgroup$ – Christopher Carl Heckman Mar 8 '16 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.