A Hamiltonian cycle in graph G is a cycle that visits every vertex in the graph exactly once before returning to the start vertex. The problem HAMILTONIAN CYCLE asks whether graph G does in fact...

A Hamiltonian cycle in graph G is a cycle that visits every vertex in the graph exactly once before returning to the start vertex. The problem HAMILTONIAN CYCLE asks whether graph G does in fact contain a Hamiltonian cycle. Assuming that HAMILTONIAN CYCLE is N P-complete, prove that the decision-problem form of TRAVELING SALESMAN is N P-complete.