# Travelling Salesman Problem

Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?

-
No. Any pair of crossing edges can be replaced with a pair of noncrossing edges, which strictly decreases the total length of the path by the triangle inequality. –  Qiaochu Yuan Mar 14 '10 at 22:51
It depends on if one is working with sites drawn in the plane and if the edges are weighted with Euclidean distances. If one has arbitrary weights and the weights do not obey the triangle inequality then in a drawing of a shortest weight tour, edges may cross. –  Joseph Malkevitch Mar 14 '10 at 23:07
There is a diagram of the argument Qiaochu gave here: ams.org/featurecolumn/archive/tsp.html –  Douglas Zare Mar 14 '10 at 23:10
But what does it mean to say that the solution has edges that cross? –  Harald Hanche-Olsen Mar 14 '10 at 23:22
The natural interpretation is that bob is talking about the Euclidean TSP. –  Douglas Zare Mar 14 '10 at 23:40