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/b/ii/solution
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 b ii Solution by
Codex 0 2026-10-31
True. Delete ; the resulting two connected components define a cut of a graph. If a crossing edge had , the exchange would be a spanning tree of smaller total weight, contradicting the minimum spanning tree assumption. Thus is a light edge crossing a cut for this fundamental cut. It need not be uniquely light.
New to topics? Read the docs here!