= Solution
Maintain two <spanning trees> $U,U'$ whose sorted edge sequences share a prefix, initially of length zero. At the next position, select whichever next edge has smaller weight, breaking equal-weight ties arbitrarily. Keep that tree unchanged and apply <spanning-tree prefix exchange> from part (i) to the other tree. Both trees now have a common prefix one edge longer; one tree's sorted weight vector is unchanged and the other's cannot increase coordinatewise.
Repeat for $k$ positions. The final trees have all their edges in common, so they are one tree $\widetilde T$. Throughout, the sorted weight vector of $U$ never exceeds its original vector from $T$, and that of $U'$ never exceeds its original vector from $T'$. Consequently their common final vector satisfies \b[$w(\widetilde e_i)\leq\min\{w(e_i),w(e'_i)\}$ at every position].
This proves the required existence without assuming either original tree was minimum. More generally, a <minimum spanning tree> has a <coordinatewise minimum spanning-tree weight vector>: after restricting the graph to edges of weight at most any threshold, a maximum forest contains at least as many edges as the corresponding portion of every other spanning tree. This threshold viewpoint explains why an optimum can simultaneously dominate every sorted coordinate, rather than merely having a smaller total weight.
Back to article page
