Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?
closed as offtopic by Ricardo Andrade, Lucia, Chris Godsil, Ryan Budney, Stefan Kohl Apr 14 '14 at 23:06This question appears to be offtopic. The users who voted to close gave this specific reason:



I've answered this in http://stackoverflow.com/questions/2444125/crossingedgesinthetravellingsalesmanproblem/2444288#2444288. 


Yes, as long as your distance does not satisfy the triangle inequality. Here is a series of points which form a shortest route under the Hamming distance. If you plot them on the plane, you will notice that they cross over. (1,1) (1,2) (4,2) (3,2) (0,2) (0,1) 

