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

At weight $y$ the edges considered are precisely the horizontal edges in row $y$. For $y=1$ all $n$ graph vertices in that row are isolated, so all $n-1$ edges are accepted. For $y\ge 2$, the first $y-1$ graph vertices in that row already belong to the one component built by earlier stages, because vertical columns $1,\dots ,y-1$ have already been processed. The other graph vertices are isolated. Thus the edges with $x<y-1$ would create a graph cycle, and all the edges with $x\ge y-1$ are accepted, successively attaching the remaining graph vertices. The rule isThe selected edges of equal weight have no cycles after the existing component is contracted, so tie ordering does not affect this conclusion. Their combined contribution to the minimum spanning tree cost is