Given a complete, weighted graph as the input to TSP, is the edge from $i$ to $j$ with minimum weight always in the solution?
2026-03-26 22:14:04.1774563244
On
Is the shortest edge always used in the solution to TSP?
122 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
Consider the four points $P(-2,0)$, $Q(0,1)$, $R(2,0)$, $S(0,-1)$ with edges weighted by the Euclidean distance. The shortest edge is $QS$ of length $2$, and a shortest circuit containing the edge $QS$ is $PQSRP$ of length $6+2\sqrt5\approx10.47$, but the shortest circuit of all is $PQRSP$ of length $4\sqrt5\approx8.94$.
Try this example. If you use edge $(1,2)$, then you must also use $(3,4)$.