How Do You Connect Every Village with the Least Cable?

Start with three villages, each pair joined by a possible route of 3, 4 or 6 km. There are three ways to join them with two routes: 3 + 4 = 7 km, 3 + 6 = 9 km and 4 + 6 = 10 km. The best leaves out the longest route. Two things in this tiny case are true for any number of villages.

The least network never has a loop. If some lines in a plan form a loop, take any one of them out: every village is still joined, since power can go round the other way, and the plan is shorter. So the best plan has no loop. A network that joins every place and has no loops is called a spanning tree: a tree because, like a real tree’s branches, its lines never grow back together. The one with the least total length is the minimum spanning tree.

With n places, a tree has exactly n − 1 lines. With no lines, every place is a group on its own: n groups. A line that closes no loop joins two places in different groups (otherwise it would close a loop), so it merges two groups into one. To get from n groups to one takes exactly n − 1 such lines. Besi and the seven villages are 8 places, so every plan with no loop has 7 lines; the puzzle is only which 7.

Here is a rule that seems too simple to work. List the routes from the shortest to the longest. Go down the list and, for each route:

• lay a line along it, unless it would close a loop;
• if it would close a loop, cross it out.

Stop when you have laid n − 1 lines. Try it on the hillside.

On the hillside, the routes of 2, 3, 4 and 5 km are laid. Besi to Deurali (6 km) is crossed out: Besi and Deurali are joined already, through Pipalbot. Pipalbot to Sano Gaun (7 km) joins the two groups grown so far. The 8 and 9 km routes are crossed out, Sano Gaun to Chisapani (10 km) is laid, and the 11, 12 and 13 km routes each close a loop. Thulo Gaun to Lekhgaun (14 km) is the seventh line: 2 + 3 + 4 + 5 + 7 + 10 + 14 = 45 km.

This rule is called Kruskal’s algorithm, after the American mathematician Joseph Kruskal, who published it in 1956. It is a greedy rule: at every step it takes what looks best right now and never goes back. Greedy rules are often wrong. Imagine notes of 25, 20, 10 and 5 rupees: pay Rs 40 by always taking the biggest note that fits, and you get 25 + 10 + 5, three notes, when two 20s would do. So why should shortest first be any better?

The proof rests on one fact. Divide the villages into two groups, any way you like. Some line of any plan must cross from one group to the other, or they would never be joined. Among all the routes crossing the divide, take the shortest; call it e.

The cut rule. Some cheapest network uses the route e.

Here is why. Take any cheapest network. If it doesn’t use e, add e to it, as on the left of Figure 26.1: with one line too many, it now has a loop through e. Walk round that loop starting along e: you cross the divide on e, and must cross back before you return, so the loop crosses the divide again, along another line, f. Take f out. The loop is broken in one place, so everything is still joined, with n − 1 lines again: a spanning tree. Its length has changed by e − f, and e was the shortest route across the divide, so e − f is zero or less. So the new network is cheapest too, and it uses e.

Now watch shortest first. Each line it lays joins two separate groups. Take one of them as one side of a divide, everything else as the other. A shorter route across this divide came earlier in the list, when its ends were in different groups too (groups only ever merge), so it would have been laid, and would now be inside a group, not crossing. So the line being laid is the shortest route across this divide, and the cut rule says some cheapest network contains it. And the swap never disturbs an earlier line: those lie inside groups, so none of them can be the f taken out. So the lines laid so far always belong to one cheapest network, and when the seventh is laid, they are it.

The crossed-out routes have their own rule, the loop rule: the longest route in any loop is never needed (if it is strictly the longest, no cheapest network uses it). Each route that shortest first crosses out closes a loop of lines laid before it, all shorter, so it is the longest in its loop.

A second rule is closer to how a line crew thinks. Start at Besi, the only place with power. Then, again and again, lay the shortest route that runs from a place with power to a place without it, until every village has power.

The lines go in a different order this time: 4 km to Pipalbot, 5 km to Deurali, 7 km to Sano Gaun, then 3 km to Thulo Gaun and 2 km to Simle, then 10 km to Chisapani and 14 km to Lekhgaun. But they are the same seven lines, the same 45 km. The cut rule explains why: take “with power” and “without” as the two sides of the divide, and each step lays the shortest route across it.

This is Prim’s algorithm, or more fairly the Jarník–Prim algorithm: the Czech mathematician Vojtěch Jarník found it in 1930, and Robert Prim found it again at Bell Laboratories in the United States in 1957. Edsger Dijkstra, whose method for shortest routes is in What Is the Quickest Way Across the Map?, found it a third time in 1959, in the same short paper as his shortest routes.

Least cable, or shortest way from Besi?

Suppose you want instead each village as close as possible to Besi along the line. Then you give each its shortest route from Besi, as Dijkstra’s method finds it. Deurali would get its own 6 km line straight from Besi, instead of being reached through Pipalbot (4 + 5 = 9 km), and Chisapani would hang off Pipalbot by the 12 km route, 16 km from Besi instead of the 21 km it is in the 45 km network. This network uses 48 km. Least cable and shortest distances are different goals. Office computer networks, which must also avoid loops, make the second choice: the Spanning Tree Protocol keeps each switch’s cheapest path to one chosen “root” switch (see Trees in Grade 10 Computing).

A new pole in the middle

So far a line could only branch at a village. What if the plan may put up a new pole anywhere, for three lines to meet? Take three villages at the corners of a triangle whose sides are all 10 km. Without a junction, the best is two sides, 20 km. With a junction at the middle, three lines of about 5.77 km each make about 17.32 km: 13.4% less line, for one extra pole.

The shortest total comes where the three lines meet at 120∘°, 120∘° and 120∘°. To see why, drill three holes in a table top at the villages, tie three strings together in a knot, thread one string down through each hole and hang the same weight on each. The weights sink as low as they can, so they leave as little string as possible on the table: the knot comes to rest where the three strings on top are shortest in total. There each string pulls the knot towards its village equally hard, and three equal pulls cancel only when they are 120∘° apart (drawn nose to tail, they must close up into a triangle with equal sides, and walking round it you turn 120∘° at each corner). The junction is then the point whose distances to the three villages add up to the least: the Fermat point of the triangle. Pierre de Fermat set it as a challenge to Evangelista Torricelli, who found it where the circles round three equilateral triangles drawn on its sides meet; his pupil Vincenzo Viviani published the solution in 1659.

It doesn’t always help. In the triangle with a wide angle (about 143∘° at Chaur), the best junction is Chaur itself (on the table, the knot is pulled right into Chaur’s hole): the plain network of two sides. The rule: if one angle of the triangle is 120∘° or more, the junction belongs at that village, and a junction saves nothing.

A network that may add junctions is a Steiner tree, and the junctions are Steiner points. With many villages, the junctions always meet in threes at 120∘°, and at most n − 2 of them are ever needed. But where to put them has no known fast method: it belongs to the family of hard problems in Algorithms for Hard Problems (Grade 12 Computing). The equilateral triangle’s 13.4% is believed to be the most that junctions can ever save on a flat map, compared with the minimum spanning tree: that is the Gilbert–Pollak conjecture. A proof announced in 1990 was later found to have a gap, and as of 2026 it is still not proved.

• What Is the Quickest Way Across the Map? The quickest route from one place, by nearest first.
• How Does a Map App Find the Quickest Route? (Grades 9–12) Searching towards the goal.
• Can You Cross Every Bridge Just Once? Walking every line of a network just once.
• Why Do Flights to America Fly Near the North Pole? Shortest lines on the round Earth.
• Graphs, Maps, Routes and Networks (Grade 10 Computing) Networks in Python, and the trees inside every search; and Grade 12’s Algorithms for Hard Problems, greedy rules that fail.
• How Do Games Build a New Maze Every Time? (Computing, Going Further 9–12) Mazes as random spanning trees.