 Solution

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.