= Spanning-tree prefix exchange
Suppose two <spanning trees> have the same first $n$ edges in nondecreasing weight order. If the first tree's next edge $e$ is no heavier than the second tree's next edge, it can be inserted into the second tree while preserving the common prefix and without increasing any sorted edge weight. If $e$ already occurs there, it ties for the next position. Otherwise its <fundamental cycle> contains an edge $f$ outside the prefix, since the prefix together with $e$ is acyclic. Every such $f$ is at least as heavy as $e$. Exchanging $f$ for $e$ preserves the <spanning tree>. Replacing a multiset entry by a no-larger entry cannot increase any <order statistic>. Tied edges can be ordered to preserve the prescribed prefix.
Back to article page
