Not an answer; just a request for clarification. <hr /> [![Tours5][1]][1] <hr /> The points are not in convex position. The optimal tour is shown in the left figure. (1) Is it "$k$-optimal" in your notation for some $k$? "Uniquely $k$-optimal"? (2) The optimal tour cannot be improved. Do the two suboptimal tours each illustrate "exchanging $2$ edges"? Or $3$ edges? Or $6$? [1]: https://i.sstatic.net/PDIN4.jpg