[SOLVED] CS Proof of Cut Property

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 SeT*Figure 1: Illustration of proof of Cut Property1