Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 8 / c

The displayed reference to index $n+1$ makes the nontrivial case $0\le n<k$; at $n=k$ the trees already agree and no further edge exists. Write $F=\{e_1,\dots ,e_n\}$ and $e=e_{n+1}$. If $e\in T^{\prime }$, its weight is at least the first nonprefix weight $w(e_{n+1}^{\prime })$ and at most that weight by hypothesis. Thus it ties for the next position, and simply ordering this tie with $e$ first gives the result.

Otherwise add $e$ to $T^{\prime }$. The resulting fundamental cycle contains an edge $f\notin F$: if its whole path lay in $F$, then $F\cup \{e\}\subseteq T$ would already contain a cycle. Every edge of $T^{\prime }\setminus F$, including $f$, has weight at least $w(e_{n+1}^{\prime })\ge w(e)$. Set $\tilde{T}=T^{\prime }-f+e$.

This is a spanning tree and still contains $F$. Its sorted order can begin with the specified prefix and then $e$, because all remaining edges have weight at least $w(e)$ and each prefix weight is at most $w(e)$. Replacing one entry of a multiset by a no-larger entry cannot increase any sorted order statistic: for every threshold, the number of entries below or equal to it cannot decrease. Hence $w({\tilde{e}}_j)\le w(e_j^{\prime })$ for every $j$. Ties may be ordered as needed; the paper prescribes nondecreasing weights, not an immutable global tie-break rule. This is spanning-tree prefix exchange.

Maintain two spanning trees $U,U^{\prime }$ 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 $\tilde{T}$. Throughout, the sorted weight vector of $U$ never exceeds its original vector from $T$, and that of $U^{\prime }$ never exceeds its original vector from $T^{\prime }$. Consequently their common final vector satisfies $w({\tilde{e}}_i)\le \min \{w(e_i),w(e_i^{\prime })\}$ 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.