Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/functional-programming-design-and-analysis-of-algorithms/8/a/ii/solution

The minimum spanning tree cut property, in its safe-edge form, says: if an edge set is contained in some minimum spanning tree, a cut of a graph respects , and is a light edge crossing a cut, then is contained in some minimum spanning tree.
Choose an MST containing . If , nothing changes. Otherwise adding creates its unique fundamental cycle. The path in between the endpoints of must cross the chosen cut; take such an edge . Since the cut respects , . Since is light, . The exchange is a spanning tree containing , with total weight no greater than that of . Minimality of forces equal optimum weight, proving the claim. Equal edge weights cause no difficulty: “safe” means belonging to some compatible optimum, not to every optimum.

New to topics? Read the docs here!