= Solution
{c}
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\ge2$, the first $y-1$ <graph vertices> in that row already belong to the one component built by earlier stages, because vertical columns $1,\ldots,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 is
$$
\boxed{(x,y)(x+1,y)\text{ is accepted exactly when }x\ge y-1.}
$$
The 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
$$
(n-1)+\sum_{y=2}^n y(n-y+1)=\frac{n(n+1)(n+2)}6-1.
$$
Back to article page
