Hamiltonian Cycle & TSP

HAM-Cycle ${\le }_p$ TSP

From the graph, it is easily observed that:

$G$ contains a Hamiltonian Cycle $⟺$ $\bar{G}$ has a traveling salesman tour of total cos t at most $0$.

Links

NP Completeness Definition

Reference

• Introduction to Algorithm