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

A precise safe-extension form of the cut lemma for minimum spanning trees is as follows. Let $F\subseteq E$ be contained in some minimum spanning tree. Let $S$ be a nonempty proper subset of $V$, and suppose no edge of $F$ crosses the cut of a graph $(S,V\setminus S)$. If $e$ is any least-weight crossing edge, thenTo prove it, choose a minimum spanning tree $T$ containing $F$. If $e\in T$, it already certifies the claim. Otherwise inserting $e$ creates a graph cycle. The other part of that graph cycle must cross the cut of a graph, so choose a crossing edge $f\in T$. It does not belong to $F$, and $w(e)\le w(f)$. Then $T-f+e$ is a spanning tree containing $F\cup \{e\}$, of weight no greater than the optimum. It is therefore also optimal.

With $F=\varnothing$, a lightest crossing edge belongs to at least one minimum spanning tree. If that edge is uniquely lightest, it belongs to every minimum spanning tree, the strict version of the minimum spanning tree cut property. With ties, “every” would be false: in an equal-weight triangle either crossing edge can be omitted from some optimum.