= Solution
Processing by increasing weight, <Kruskal's algorithm> accepts $df$ of weight one and $cf$ of weight two, then rejects $cd$ of weight three because its endpoints are already connected. It accepts $ac$, $eh$, $fh$, skips $de$, accepts $be$, skips $bc$, and accepts $eg$. Seven accepted edges now connect all eight vertices.
The resulting <minimum spanning tree> is
$$
\boxed{\{df,cf,ac,eh,fh,be,eg\},\qquad w(T)=1+2+4+5+6+8+10=36.}
$$
The remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/algorithms-minimum-spanning-tree.png]
{title=Minimum spanning tree of weight 36 and its component-merging construction}
{description=The solution highlights the seven selected edges. The second panel distinguishes the six distinct first-round choices from the joining edge fh selected in the second round.}
Back to article page
