We choose s = Be in Example 15.1.2; this choice is motivated by the fact that the sum of the two smallest edge weights is maximal for this vertex. We obtain the s-tree B shown in Figure 15.3; note that B is the minimal spanning tree T given in Figure 15.2, with the edge BeNu added. Hence w(TSP) ≥ w(B) = 186 + 44 = 230.
