On this page
In February 1956, Joseph B. Kruskal published a three-page paper with a rule you can run with a pencil: keep taking the cheapest link that does not close a loop. It was titled "On the shortest spanning subtree of a graph and the traveling salesman problem" (Crossref record of the paper). Today it is taught as Kruskal's algorithm, and it is a classic example of a greedy method that can be proved correct.
Who was Joseph Kruskal?
Kruskal was born in New York City on 29 January 1928. He studied mathematics at the University of Chicago and earned his PhD at Princeton in 1954 (MacTutor biography). He lectured at the University of Wisconsin from 1956 to 1959, then joined Bell Laboratories in Murray Hill, New Jersey, in 1959 and stayed until he formally retired in 1993 (same source).
His paper appeared in the Proceedings of the American Mathematical Society, volume 7, pages 48–50. Its only reference is Otakar Borůvka's 1926 paper "On a minimal problem" (Crossref). Borůvka had tackled the same question after a friend at the firm West-Moravian Powerplants posed it as a problem about connecting cities (MacTutor on Borůvka). Questions like these belong to graph theory, which goes back to Euler and the seven bridges of Königsberg.
How does Kruskal's algorithm work?
A graph is a set of points (vertices) joined by lines (edges), and here each edge carries a cost, or weight. A minimum spanning tree is "a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight" (Wikipedia: minimum spanning tree). A spanning tree on n vertices always has exactly n − 1 edges (same source).
Kruskal's rule has three steps:
Sort all the edges from cheapest to most expensive.
Take the next edge. If its two ends are already connected by edges you have kept, skip it, because it would close a loop. Otherwise, keep it.
Stop when you have kept n − 1 edges.
It is greedy: it always grabs the cheapest acceptable edge and never undoes a choice.
A worked example: six villages, nine possible cables
Six villages, A to F, need to be joined by cable. The possible links and their costs (in lakh rupees, made-up numbers) are: E–F 1, B–C 2, D–E 3, B–D 4, C–D 6, A–B 7, C–E 8, D–F 9, A–C 10. Six villages need 6 − 1 = 5 cables.
E–F (1): keep. Groups: {E, F}.
B–C (2): keep. Groups: {E, F}, {B, C}.
D–E (3): keep. Groups: {D, E, F}, {B, C}.
B–D (4): keep. The two groups merge into {B, C, D, E, F}.
C–D (6): skip. C and D are already connected through B, so this edge would close the loop B–C–D.
A–B (7): keep. That is five edges, so stop.
The tree costs 1 + 2 + 3 + 4 + 7 = 17 lakh. Laying all nine cables would cost 50.
Why does a greedy choice give the cheapest tree?
The proof rests on the cycle property: if one edge in a loop is heavier than every other edge in that loop, it cannot be part of any minimum spanning tree (Wikipedia: minimum spanning tree). Kruskal only skips an edge when it would close a loop made of edges already kept. Those edges came earlier in the sorted list, so they cost less, and the skipped edge is the heaviest in its loop. In the example, C–D (6) is heavier than B–C (2) and B–D (4).
So no skipped edge belongs to a minimum spanning tree. With all weights different, as here, that tree is unique (same source), and its n − 1 edges must be exactly the n − 1 Kruskal kept.
If your total comes out too high, look for a missed loop or an unsorted list. The Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning, so you can see which step went wrong.
How is Kruskal's algorithm different from Prim's?
Prim's algorithm reaches the same kind of answer from the other side. It starts at one vertex and keeps adding the cheapest edge that leaves the tree it has grown (Wikipedia: Prim's algorithm). Vojtěch Jarník found it in 1930, and Robert Prim published it again in 1957 (same source) in the Bell System Technical Journal (Crossref record).
In code, Kruskal's running time is O(E log E) for E edges, and the sorting step dominates; the loop test uses a disjoint-set (union-find) structure (Wikipedia: Kruskal's algorithm). On paper, use this checklist for either method:
Count the vertices and write "need n − 1 edges".
For Kruskal, sort the full edge list first.
For Prim, look only at edges leaving the tree you have grown.
Write "skip, loop" next to every rejected edge.
If words like "cycle" or "cut" still feel shaky, the Fermi Concept Library gives each concept in mathematics and computing its own lesson. For two more algorithms worth tracing by hand, try Euclid's division algorithm for the HCF and the PageRank algorithm behind early Google.
