= Solution
Write each undirected <edge> with its smaller endpoint first. <Kruskal's algorithm> orders candidates first by weight and then lexicographically:
$$
\begin{array}{c|r|l}
\text{edge}&\text{weight}&\text{action}\\\hline
(4,6)&1&\text{add}\\
(1,3)&2&\text{add}\\
(3,4)&2&\text{add}\\
(1,4)&3&\text{reject: closes a cycle}\\
(4,5)&3&\text{add}\\
(5,6)&3&\text{reject: closes a cycle}\\
(1,2)&4&\text{add and finish}
\end{array}
$$
Thus the requested addition order is
$$
\boxed{(4,6),\ (1,3),\ (3,4),\ (4,5),\ (1,2),}
$$
and the <minimum spanning tree> has total weight \b[$12$]. Five accepted edges connect all six vertices, so the remaining weight-four edges need not be scanned.
Back to article page
