without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?
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 &gt; 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 &gt; 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^*)$.