= Solution
{c}
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:
$$
\boxed{(x,y)(x,y+1)\text{ is accepted exactly when }y\ge x.}
$$
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
$$
\sum_{x=1}^{n-1}\left(x+\frac12\right)(n-x)=\frac{n(n-1)(2n+5)}{12}.
$$
Back to article page
