Correctness of GENERIC-MST

The correctness of GENERIC-MST follows from the Greedy-Grow Lemma.

• Proof by induction. The initial set $T=\emptyset$ is a subset of any MST.
• At each step, GENERIC-MST adds an edge that is necessarily part of some MST (by the Greedy-Grow Lemma).
• So, when the set T is a spanning tree, it must be an MST (it is a subset of some MST, itself).