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 / i / Solution

A cut of a graph is a partition $(S,V\setminus S)$ into two nonempty vertex sets. An edge crosses it when its endpoints lie on opposite sides. An edge set respecting a cut contains no crossing edge. A light edge crossing a cut has minimum weight among all crossing edges; there can be several tied light edges. These definitions concern the graph's weighted edges, independently of any particular spanning tree.