How do you reduce Vertex cover to Hamiltonian Cycle? <p><a href="http://i.stack.imgur.com/HH8Bp.jpg" rel="nofollow">This is the example the book uses</a></p> <p>The book I'm using is Introduction to Algorithms 3rd edition. Anyway they explain how to reduce Vertex Cover to Hamiltonian Cycle to prove Hamiltonian Cycle is NP complete. I understand that for every edge in the vertex cover you need to create a widget, and I understand that for every member of the vertex cover you have a selector. However what's giving me problems is the method of moving through the widgets. There is a formula but it seems very arbitrary to me. Could anyone explain it in simpler terms? I'd much appreciate it.</p> <p>Edit: I also understand there exist three different ways in which you have traverse a widget.</p>