# Does the shortest path have no crossings?

Suppose $A_1,A_2,A_3,\ldots,A_n$ are distinct points in the plane. A closed path on those points is formed from a permutation of the points, with line segments drawn between successive points (and with a segment connecting the last point to the first, to make the path “closed”). For the six points pictured below on the left, the next three pictures indicate paths corresponding to the permutations $A_1A_2A_3A_4A_5A_6$, $A_1A_3A_6A_2A_4A_5$, and $A_1A_3A_6A_2A_5A_4$. Prove: No matter how $n$ distinct points $A_1,A_2,A_3,\ldots,A_n$ are placed in the plane, the shortest closed path on those points has no crossings.

• Use triangle inequality theorem. – hjpotter92 Mar 6 '13 at 9:15
• Triangle inequality and induction on the number of crossings in your shape. – dtldarek Mar 6 '13 at 9:19

## 2 Answers

If $a, \ldots, b, c, \ldots, d, e, \ldots a$ is a closed path with $bc$ and $de$ intersecting, show that $a, \ldots b, d, \ldots c, e, \ldots a$ is shorter.

Given $n$ points in the plane, there are a finite number of ways of connecting them in to a loop. Note that each loop has a finite total length. Suppose we begin with a loop $X$ which has a crossing. Let a crossing of $X$ be the line segments $[a,b]$ and $[c,d]$. We can replace the loop $X$ by two other graphs $X'$ and $X''$ given by removing the line segments above and replacing them with $[a,c]$ and $[b,d]$ for $X'$ and with $[a,d]$ and $[b,c]$ for $X''$. Precisely one of $X'$ and $X''$ will be a loop.

WLOG suppose it is $X'$ which is a loop. It should be clear (but you can prove this using the triangle inequality) that by 'uncrossing' two crossed segments as was done above, the total length of the loop has been decreased. There are now two possible cases for the state of $X'$. Either $X'$ now has no crossings, in which case we are done as we have shown that $X$, with crossings, did not have minimal length, or $X'$ still has crossings (possibly new ones added in by the uncrossing). In the second case, simply repeat the above to get a new loop with shorter total length. After each repetition, the total length is reduced, and there are only a finite number of total lengths that a loop can have. It follows that we will eventually reach a loop with 0 crossings which has total length less than the original loop with a crossing.