C35-Approximation-Algorithms/35.2-5.md
Suppose that the vertices for an instance of the traveling-salesman problem are points in the plane and that the cost c(u,v) is the euclidean distance between points u and v. Show that an optimaol tour never crosses itself.
Cost function based on euclidean distance satisfies the triangle-inequality, s.t.:
c(u,v) <= c(u,w) + c(w,v)
Assume: The tour corsses itself.
Let (u,v) and (w,x) be corssing edges, u -> v -> w -> x the assumed optimal tour and P the crossing point of (u,v) and (w,x).
Based on the triangle-inequality its:
c(x,v) <= c(x,P) + c(P,v)
Thus we can derive:
c(u,P) + c(P,w) + c(x,P) + c(P,v) + c(u,w) + c(w,v) >= c(u,w) + c(x,v) * c(u,x) + c(w,v)
Based on our definition its c(u,P) + c(P,v) = c(u,v) and c(x,P) + c(P,w) = c(x,w)
Therefore its c(u,v) + c(v,w) >= c(u,w) + c(x,v) which denotes in combination with (u,x) and (v,w) a shorter tour then the original one. Contradiction. q.e.d