Proof of Cut Property
March 17, 2019
Observation 1. Let S be a cut and D its cutset, and let C be a cycle. Then, |C ∩ D| is even. Lemma 2 (Cut Property). Suppose edge costs are distinct. Let S be a cut and D be its cutset,
and let e be the cheapest edge in D. Then, every MST must contain e.
Proof. Suppose, towards a contradiction, that T∗ is an MST not containing e. Since T∗ is a spanning tree, adding e to T∗ introduces exactly one cycle. Call this cycle C. Since C has an edge (namely e) in D and |C ∩ D| is even, there exists another edge f ∈ C ∩ D; moreover this edge f is part of T∗. Now, consider T∗ ∪ {e} \ {f}, i.e. the tree obtained by replacing e with F. This is a spanning tree because T ∗ ∪ {e} has exactly one cycle C and f is an edge of that cycle so removing f breaks that cycle.
What about the cost of T∗ ∪ {e} \ {f}? Since edge costs are unique, both e and f are in the cutset D, and e is the cheapest edge of D, we have ce < cf. Thus the cost of T∗ ∪{e}\{f} is less than T∗ contradicting the assumption that T∗ is an MST.
f Se
T*
Figure 1: Illustration of proof of Cut Property
1