Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/functional-programming-design-and-analysis-of-algorithms/7/a/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 7 a Solution by
Codex 0 2026-10-25
The minimum spanning tree cut property says: if a cut of a graph respects an edge set contained in some minimum spanning tree, a minimum-weight edge across that cut is safe to add to , meaning that some minimum spanning tree contains together with that edge. Respecting means no edge of crosses the cut. In particular, any lightest cut edge belongs to some minimum spanning tree; a uniquely lightest cut edge belongs to every minimum spanning tree.
For the exchange argument, take a minimum spanning tree containing . If it lacks the chosen edge , add to create its fundamental cycle. The remaining route between 's endpoints crosses the cut at some edge , with . Since the cut respects , . Replacing by preserves a spanning tree, retains , and cannot increase weight. Hence it is also minimum. Strict inequality would contradict minimality, which gives the unique-lightest assertion.
For an illustration, take a triangle with weights , , . Across the cut , is the unique lightest edge and must be in every minimum spanning tree. The minimum tree is , of weight . With tied light edges, the existence assertion need not mean that every minimum spanning tree contains the particular tied edge chosen.
New to topics? Read the docs here!