= Solution
For a connected weighted <undirected graph>, <Kruskal's algorithm> begins with each vertex as a separate component and no selected edges. Sort all edges into nondecreasing weight order. Inspect them in that order and add an edge exactly when its endpoints lie in different current components. Merge those components after an addition; stop once $|V|-1$ edges have been accepted. A <disjoint-set data structure> implements the component tests and merges.
The accepted edges always form a <forest>, because an edge whose endpoints were already connected is rejected. To prove optimality, use the invariant that some <minimum spanning tree> contains every accepted edge. It holds initially. Suppose the next accepted edge is $e=uv$, and let $T$ be a <minimum spanning tree> extending the current <forest>. If $e\in T$, nothing changes. Otherwise adding $e$ to $T$ makes a unique <graph cycle>. The <graph path> from $u$ to $v$ in $T$ must cross the <graph cut> between the current component of $u$ and the remaining vertices, so that <graph cycle> contains an edge $f$ crossing this <graph cut>. No accepted edge crosses it. Furthermore $w(e)\leq w(f)$: any strictly lighter crossing edge would already have been processed and accepted, since its endpoints could not then have been connected without also being connected now.
Replace $f$ by $e$. The resulting <spanning tree> still contains all previously accepted edges and has cost at most that of $T$, so it too is a <minimum spanning tree>. This is the <exchange argument> establishing the invariant. At termination the selected edges themselves form a <spanning tree>, hence
$$
\boxed{\text{Kruskal's algorithm returns a minimum spanning tree}.}
$$
Equal weights cause no difficulty; they may give several optima. On a disconnected <graph>, processing all edges instead returns a <minimum spanning forest>. Sorting costs $O(|E|\log |E|)$, with near-linear additional cost using an efficient <disjoint-set data structure>.
Back to article page
