= Solution
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>, then
$$
\boxed{F\cup\{e\}\text{ is contained in some minimum spanning tree}.}
$$
To 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.
Back to article page
