Prove the following claim on Hamilton Path?
Try to prove instead (without induction) that if the algorithm returned false, there is no hamilton path.
Hint: there must be two parallel nodes. Can we reach one from the other?