Suppose towns must be linked by roads, each possible road has a cost, and every town must be reachable. The cheapest network has no cycles (a cycle always has a removable road), so it is one of the trees inside the graph. Finding the cheapest one is easy, by a greedy rule.
Key idea
A spanning tree of a connected graph is a tree that uses all of its vertices; with $n$ vertices it has $n - 1$ edges. In a weighted graph, a minimum spanning tree has the least total weight. Kruskal's algorithm: go through the edges from cheapest to most expensive, and add each edge unless it would close a cycle with the edges already chosen; stop at $n - 1$ edges.
Why it works
Why does greed not backfire? Split the vertices into any two groups. The cheapest edge crossing between the groups belongs to some minimum spanning tree: if a tree avoided it, adding it would create a cycle that crosses the split somewhere else, at an edge at least as expensive, and swapping the two edges would not raise the cost. Every edge Kruskal adds is the cheapest crossing between the component it joins and the rest, so it never makes a choice it regrets. Skipping cycle-closing edges is what keeps the result a tree.
Worked examples
Worked example: Running Kruskal's algorithm
For the graph above (weights: $DF\,1$, $BE\,2$, $AC\,3$, $AB\,4$, $BC\,5$, $BD\,6$, $CE\,7$, $DE\,8$, $EF\,9$), find a minimum spanning tree.
- $DF$ ($1$): add. $BE$ ($2$): add. $AC$ ($3$): add. $AB$ ($4$): add; now $A, B, C, E$ are connected.
- $BC$ ($5$): $B$ and $C$ are already connected through $A$, so it would close the cycle $B - A - C - B$. Skip.
- $BD$ ($6$): joins $\{D, F\}$ to the rest. Add. That is $5 = 6 - 1$ edges: stop.
- Total weight $1 + 2 + 3 + 4 + 6 = 16$.
Answer: $DF, BE, AC, AB, BD$; weight $16$
Worked example: Your turn to pick
Use the "learner" version below: click the edge Kruskal's algorithm should consider next. What happens if you click an edge that closes a cycle?
- The visual explains that it would close a cycle and names the cycle.
- The rule to remember: cheapest first, but only if its two ends are not yet connected.
Answer: It is rejected, with the cycle shown.
Common mistake
Adding the cheapest edge even when it closes a cycle, or stopping early. In the example, $BC$ is cheaper than $BD$, but adding it would create a cycle and leave $D$ and $F$ cut off. And a "tree" with fewer than $n - 1$ edges does not reach every vertex. Check: before adding an edge, ask whether its ends are already connected; at the end, count $n - 1$ edges.
Prim's algorithm grows a single tree instead: start at any vertex, and repeatedly add the cheapest edge with exactly one end in the tree. It finds a minimum spanning tree too.