without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?

In the text book, Introduction to Algorithm, 3rd Edition.

In the chapter, Approximation Algorithms and for the problem Travelling Salesman Problem, the author says:

I am wondering how triangle inequality gives rise to this assertion? It seems that this property is not that important, as I searched through the rest of this section, it does not appear.

Here is what these lecture notes have to say. We can reduce HAMILTONIAN-PATH to MIN-TSP-TOUR in the following way: give the weight $1$ for edges in the original graph, and $B$ (for some $B > 1$ to be chosen later) for edges not in the original graph. If the original graph had a Hamiltonian path, then the new path has a tour of length at most $n$, and otherwise any tour has length at least $n-1+B$. Thus any approximation algorithm with ratio better than $n/(n-1+B)$ would solve HAMILTONIAN-PATH. Choosing $B = 1 + (c-1)n$, we get then any algorithm with ratio better than $1/c$ would solve HAMILTONIAN-PATH. This is true for any $c > 1$, so MIN-TSP-TOUR cannot be approximated to any constant ratio.

Here is where the triangle inequality comes in in Christofides' algorithm. The algorithm is at follows:

• Construct a minimum spanning tree $T$.

• Find a minimum matching $M$ between the set $O$ of odd-degree vertices in $T$.

• Remove edges from $T\cup M$ to obtain a Hamiltonian cycle $H$.

The analysis goes like this. Suppose $H^$ is a Hamiltonian cycle of weight $w(H)$. Then $w(T) \leq w(H^)$ and $w(H) \leq w(T \cup M) \leq w(T) + w(M) \leq w(H^) + w(M)$. So far we haven't used the triangle inequality. Now take $H^$ and replace paths from adjacent vertices $a,b \in O$ on $H^$ with direct edges. The triangle inequality implies that the resulting cycle $H^{}$ satisfies $w(H^{}) \leq w(H^)$. We can partition the cycle into two matchings $M_1,M_2$ satisfying $w(M_1) + w(M_2) = w(H^{})$, and so $w(M) \leq \min(w(M_1),w(M_2)) \leq w(H^{}) \leq w(H^)$. We conclude that $w(H) \leq w(H^) + w(M) \leq 1.5 w(H^*)$.

StackExchange Computer Science Q#16143, answer score: 5