Greedy-Grow Lemma

Lemma: If T is a subset of some MST, and C is some cut that doesn't share any edges with T, then there is some MST containing T and the minimum cost edge e^* in C.

Proof: Very standard trick. Let T^* be the MST that contains T. If $e^* \in T^*$, we're done. If not, consider the set of edges $T^* \cup \{ e^*\}$. It must have a cycle including e^* and some other edge e (maybe more than one) in C. By definition, $w(e^*) \le w(e)$. Delete e from T^*.

• Is the resulting set $T^*\cup\{e^*\}-\{e\}$ still a spanning tree?

• What is its cost compared to T^*?