The travelling salesman problem for a regular n-gon The TSP asks, given a finite set $V$ of points in $\Bbb R^2$, to find the shortest path that passes through all points and returns to the starting point. Trivially, one reduces to the case of a path that consists only of straight lines between elements of $V$, but the resulting combinatorial problem is quite difficult in general, and TSP is known to be NP-complete.
However, it is solvable in many concrete cases, and I am sure that the $n$-gon is one of them. It is intuitively reasonable that the perimeter of a regular $n$-gon is the solution to TSP on the vertices, but how would you prove it?
Can the proof be generalized to any convex polygon?
 A: Take a path $P$ through all the points in a convex polygon. It can be specified by enumerating the vertices it touches in order: $P=\{v_1, \cdots, v_n\}$.


*

*If it isn't the perimeter, it cuts itself at some point in the interior. Proof: Take a segment $[v_i, v_{i+1}]$ that's not a side. It splits the polygon into two parts. They must be joined together by another segment for $P$ to be closed. Therefore, there's another segment that intersects it.

*Let $[v_i,v_{i+1}]$, $[v_j,v_{j+1}]$ be two segments that intersect. Then, the path obtained by exchanging $v_{i+1}$ and $v_j$ (that is, $P'=\{v_1,\dots,v_i,v_j,v_{j-1}\dots,v_{i+1},v_{j+1},v_{j+2},\dots,v_n\}$) is shorter than $P$. Proof: The lengths of $P$ and $P'$ are the same except for the difference between $d(v_i,v_{i+1})+d(v_j,v_{j+1})$ and $d(v_i,v_j)+d(v_{i+1},v_{j+1})$. The second should be smaller because it uncrosses the segments.
It follows that the perimeter is the solution to the TSP for convex polygons, because for any other path you can uncross any two intersecting segments and get a shorter one.

Note: As stated in the comments, this proof works for non-degenerate convex polygons. In the degenerate case, we can remove the degenerate points and the solution for the resulting polygon will be a solution for the original one.
