Question:
Algorithms Problem
Suppose that the vertices for an instance of the travelling salesman problem are points in a plan and that the cost c(u; v) is the Euclidean distance between points u and v. Show (i.e., prove) that an optimal tour never crosses itself.