Past exam of the short options course of the University of Oxford / 2021 / 7 / a / 2 / Solution

At weight $x+1/2$, column $x$ is considered just after horizontal row $x$. At this point its first $x$ graph vertices already lie in the component built so far, while graph vertices above them in that column are isolated. Consequently vertical edges with $y<x$ create a graph cycle, while those with $y\ge x$ attach the isolated graph vertices in a chain:Together with the horizontal rule this gives an induction on the alternating row and column stages and justifies the component description used in both numbered answers. The vertical contribution to the minimum spanning tree cost is