Proof that traveling salesman problem is NP Hard
Pre-requisite:
Problem –
G(V, E)
K
Explanation –
G
- Let us assume that the graph G contains a Hamiltonian Cycle, traversing all the vertices V of the graph. Now, these vertices form a TSP with Since it uses all the edges of the original graph having cost c(e)=1. And, since it is a cycle, therefore, it returns back to the original vertex.
- We assume that the graph G’ contains a TSP with cost, . The TSP traverses all the vertices of the graph returning to the original vertex. Now since none of the vertices are excluded from the graph and the cost sums to n, therefore, necessarily it uses all the edges of the graph present in E, with cost 1, hence forming a hamiltonian cycle with the graph G.
G’
G