# np complete – Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

Suppose your original graph $$G$$ has a Hamiltonian cycle $$C$$.
Then the cost of the tour induced by $$C$$ in the new graph $$G’$$ you defined is indeed $$0$$ and conversely, any TSP tour of cost $$0$$ can only use edges of cost $$0$$ as you did not introduce any edges with a negative cost.

Adding the loops does not change this, so the reduction works out if we are willing to allow non-simple graphs which isn’t done usually as the definition of the TSP asks for a tour visiting each vertex exactly once, i.e. no valid tour would include loop edges anyways.
Given this, we also see that you can remove the loop edges in $$G’$$ to make it a simple graph to obtain an equally valid reduction.
From a technical standpoint this doesn’t make much of a difference but since people like simple graphs, I would personally prefer the reduction yielding a simple graph.