A widget and B widget These two widgets are pieces of graphs that enforce certain properties, and they are used in the reduction below. And then the graph G will have a Hamiltonian-cycle.
G contains a Hamiltonian-cycle.
And this reduction can be performed in polynomial time. And e m and e m correspond to the variable x m and , respectively. The idea is that if the Hamiltonian-cycle takes edge e m , the variable x m is assigned the value 1. If the Hamiltonian-cycle takes edge e m , x m is assigned the value 0. Each pair of these edges forms a two-edge loop.