Minimum Spanning Tree: Kruskal and Prim

Press Twelve villages and step through Kruskal. It goes through the 66 possible roads shortest first, so K–L, 13.89 km, goes in at once, and C–D and B–C are refused because the path drawn in red already joins their ends. Switch to Prim, which grows one network out from A. It takes the roads in another order, K–L last of all, refuses the same two, and ends on the same 11 roads and the same 199.04 km. Both are obeying one rule, the cut property: split the points into two groups any way you like, and the shortest road between the groups belongs to the minimum spanning tree, as long as no two roads are the same length. Leave it out, and the tree's own path between that road's two ends crosses the gap somewhere on a longer road; swap the two and the tree gets shorter. Prim's shaded network is one side of such a cut at every step. Now press Nearest neighbour. It is Prim's loop with one change, looking out from the last village reached instead of from the whole network, and at its third step it takes D–F, 17.96 km, while A–C, 17.67 km, crosses the cut. It walks past A–C seven more times and finishes 10.76% longer. Otakar Borůvka, who solved the problem first, in 1926, with the electricity network of southern Moravia in mind, stated it for points whose “mutual distances are different”: the same condition, and the one under which Kruskal and Prim cannot disagree.

Press A ring of towns. Ten towns stand round a lake, and the tree is the shore road with one stretch left out: the widest gap, between J and A. Those two are 25.89 km apart in a straight line and 128.30 km apart along the tree, 4.96 times as far, because the only route from one to the other is the entire network. The dashed purple line marks the pair; drag any town and the page finds the new worst one. A minimum spanning tree makes the total as small as it can be and promises nothing about the distance between any two towns. Building the 25.89 km road as well would make the trip from A to J a straight one. Whether that is worth the extra road is a question about journeys, which is the shortest-path problem, and the page on Dijkstra's algorithm takes it from there.

Press Three towns. They stand 40 km apart, so the tree is 80.00 km. A junction in the middle, where three roads meet at 120°, joins them with 69.28 km, 13.40% less, which is 1 − √3/2. Press Four towns on a square and two junctions save 8.93%. Back on the triangle, drag C down towards A and B: once the angle at C passes 120° the junction slides into C, and from there no junction helps at all. Finding the best junctions is the Steiner tree problem. In 1968 Edgar Gilbert and Henry Pollak conjectured that the equilateral triangle is the worst case, that no set of points in the plane has a Steiner tree shorter than √3/2 of its minimum spanning tree. Du and Hwang published a proof in 1990. In 2010 Innami and three colleagues published evidence that its key step fails, and in 2012 Ivanov and Tuzhilin, who had been pointing at gaps in it since 2002, wrote that the conjecture is still open. A 2025 collection of open problems on Steiner trees still lists it as open. Nobody knows whether some arrangement of points can save more than the triangle's 13.40%.