= Solution
The <minimum spanning tree cut property> says: if a <cut of a graph> respects an edge set $A$ contained in some <minimum spanning tree>, a minimum-weight edge across that cut is safe to add to $A$, meaning that some minimum spanning tree contains $A$ together with that edge. Respecting $A$ means no edge of $A$ crosses the cut. In particular, any lightest cut edge belongs to some minimum spanning tree; a uniquely lightest cut edge belongs to every minimum spanning tree.
For the <exchange argument>, take a minimum spanning tree $T$ containing $A$. If it lacks the chosen edge $e$, add $e$ to create its <fundamental cycle>. The remaining route between $e$'s endpoints crosses the cut at some edge $e'$, with $w(e')\geq w(e)$. Since the cut respects $A$, $e'\notin A$. Replacing $e'$ by $e$ preserves a spanning tree, retains $A$, and cannot increase weight. Hence it is also minimum. Strict inequality would contradict minimality, which gives the unique-lightest assertion.
For an illustration, take a triangle with weights $w(ab)=1$, $w(ac)=2$, $w(bc)=3$. Across the cut $\{a\}\mid\{b,c\}$, $ab$ is the unique lightest edge and must be in every minimum spanning tree. The minimum tree is $\{ab,ac\}$, of weight $3$. With tied light edges, the existence assertion need not mean that every minimum spanning tree contains the particular tied edge chosen.
Back to article page
