How did seven bridges start the maths behind Google Maps?

The full story

This is the episode's narration, word for word. Headings jump to that point in the video.

Seven bridges, one walk 0:00

Here's a puzzle. A river splits around an island, and seven bridges join the island, the two banks and a piece of land to the east. Can you go for a walk that crosses every bridge exactly once? Start anywhere, finish anywhere, no swimming. Some said it couldn't be done, some weren't sure, and nobody claimed to have done it. So is it just hard, or impossible? And how could anyone prove that something is impossible?

Königsberg 0:31

The city was Königsberg, in Prussia, on the river Pregel. At its heart was an island called the Kneiphof, home to the cathedral and the old university. Its bridges had names, like the Blacksmiths' Bridge and the Honey Bridge. And by the 1730s, the walking puzzle was said to be well known.

Try it 0:53

So try it. From the south bank, cross to the island, then up to the north bank, back to the island, down to the south bank, out to the east, and up to the north bank again. That's six bridges, and the seventh, from the island to the east, is out of reach. Start somewhere else, and you get stranded somewhere else. You could list every possible walk, but that's laborious, and hopeless for a city with more bridges.

A letter from St Petersburg 1:22

The man who settled it was Leonhard Euler, a Swiss mathematician at the Academy in St Petersburg. He presented his answer in August 1735, aged twenty-eight. Oddly, he didn't rate it. He told the mayor of Danzig the solution "bears little relationship to mathematics". But to an Italian correspondent he admitted it was worth a look, precisely because neither geometry, nor algebra, nor counting seemed able to crack it.

Throw away the map 1:56

Euler's first move was to throw away what doesn't matter: how long the bridges are, the shape of the island, how far you walk. Only what connects to what. He gave each piece of land a letter, A for the island, and wrote a walk as a string of letters. Our stranded walk is B, A, C, A, B, D, C: six crossings, seven letters. Crossing all seven bridges would take exactly eight.

In one side, out the other 2:26

Now the key idea. Watch one piece of land. Every time your walk passes through it, it uses two bridges, one in and one out. So if you're just passing through, the bridges get used up in pairs. With an odd number of bridges, one is always left over, and the only way to use it is to start there, or finish there.

Nine letters, eight slots 2:50

So count Königsberg's bridges. The island has five, and the other three places have three each. All four are odd, but a walk has only one start and one finish, so at most two places can be odd. In Euler's letter code, the island needs three, the others two each. That's nine letters, and seven bridges only leave room for eight. So it isn't hard: it's impossible, for anyone who will ever try.

The rule for every river 3:21

Euler didn't stop at seven bridges. His paper, in Latin, was printed in 1741, in a volume dated 1736, and it gives a rule for any river and any number of bridges. More than two odd places, no walk. Exactly two, and you can do it, starting at one of them. None, and you can start anywhere. Euler made the impossible case airtight, but a full proof of the possible cases came later, from the German mathematician Carl Hierholzer. He died before writing it down, and colleagues published it from memory in 1873.

Dots and lines 4:04

Today we draw it as dots and lines: each place a dot, called a vertex, each bridge a line, called an edge. Euler never drew it like that; his figures were maps. Count the lines at every dot and each line gets counted twice, once at each end, so odd dots always come in pairs. Make the dots stations, people or web pages, and it's a graph. Euler's paper is often called the first in graph theory.

Hamilton's dodecahedron 4:35

Now change one word. Instead of every bridge, visit every place exactly once. In 1856 or 1857, the Irish mathematician William Rowan Hamilton invented a game on a dodecahedron: travel its edges and visit all twenty corners once, then return home. A London toy company sold it from 1859. It flopped, and he was reportedly paid twenty-five pounds. But a route through every dot is still called a Hamiltonian path.

Easy to check, hard to find 5:13

Euler's question has a shortcut: count the odd dots. Hamilton's has no shortcut anyone has found. Checking a route someone hands you is easy, but finding one can mean trying orders. Just twenty places have about 2.4 billion billion of them. Cleverer methods do better, but every one known still explodes as you add places. Whether a fast method exists is the P versus NP question, one of the Clay Institute's million-dollar Millennium Prize Problems, and it's still unsolved.

Twenty minutes in Amsterdam 5:50

Now give every line a length, and ask what everyone with a car asks: what's the shortest way? In 1956, the Dutch programmer Edsger Dijkstra needed a demonstration for a new computer in Amsterdam. He chose the shortest route between two Dutch cities, on a map of sixty-four towns. He designed the method in about twenty minutes, on a café terrace with his fiancée, without pencil or paper. It was published in 1959.

Nearest first 6:24

It rests on one fact. If a town is on the shortest route to your goal, then the stretch from the start to that town is a shortest route too. So you work outwards, settling places in order of distance, nearest first, until you reach the goal. A settled distance can't be beaten later, because any other way there would have to pass through somewhere at least as far away.

Watch it run 6:49

Here's a small network, in minutes. From S, the neighbours get provisional times: A four, B two. B is nearest, so settle it, and through B, A drops to three. Settle A, and C drops to eight. Then C, then D at ten, and the goal, T, at twelve. The direct road to A looked best, but the detour through B was quicker, and the method found that without trying every route.

Aim at the goal 7:20

Dijkstra's method spreads like a ripple, even straight away from where you're going. In 1968, Peter Hart, Nils Nilsson and Bertram Raphael, at the Stanford Research Institute in California, showed how to aim it. Their example was cities and roads: a road can never be shorter than the straight line, as the crow flies, so that's a safe guess to steer by. It's called A star, and it still guarantees the shortest route.

A continent of junctions 7:52

But real maps are enormous. A standard test map of Western Europe has eighteen million junctions. Plain Dijkstra looks at over nine million of them for an average random trip across the map, taking about two seconds. And A star barely helps on real roads, because for travel time the safe guess must assume top speed all the way, which is far too cautious to steer by.

Shortcuts 8:19

The trick is to do the hard work once, in advance. A method called contraction hierarchies, from Karlsruhe in Germany in 2008, ranks every junction by importance. It removes the least important first, adding a shortcut wherever that would break a shortest route. Then each trip is two searches, one from each end, that only climb toward more important junctions until they meet. On that European map, it looks at about 280 junctions, roughly twenty thousand times faster.

So what does Google use? 8:56

So is this what Google Maps does? Nobody outside the company knows exactly. A 2015 survey by eight leading researchers says companies tend to be secretive about their algorithms. Where it's public, it's the same trick of doing the hard work in advance: an OpenStreetMap planner uses contraction hierarchies, and by 2015 Google had been using one called Transfer Patterns for public transport since 2010. Google even named a graph-computing system after Königsberg's river: Pregel.

The bridges today 9:33

And the bridges? Königsberg was bombed in 1944, taken by the Soviet army in 1945, and renamed Kaliningrad; it's now Russian, wedged between Lithuania and Poland. In 2000, Peter Taylor, of the Australian Mathematics Trust in Canberra, went to check. He found that two of Euler's bridges are simply gone, two sites are now crossed by a Soviet-era highway, and three bridges still stand, though accounts differ on what the war destroyed and how original the survivors are. Count only the crossings at Euler's seven old sites, and just the island and the eastern land, itself an island, have odd counts. So on the old sites the walk now works, from one island to the other.

Impossible, for certain 10:25

Think about what Euler really did. Nobody could try every walk in every possible city, yet by counting ins and outs, he proved the walk impossible for anyone, ever. From that line of thinking grew graph theory, the route finder in your pocket, and a million-dollar question still open. That's the power of a proof. So here's a bigger question. If a proof can settle something forever, can every true statement be proved? Can maths prove everything?

Sources

Every factual claim in the episode is tied to one of these. Spotted an error? Tell us.

1. Leonhard Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii… — cantab.net
2. Wikipedia, "Kneiphof" (read 2026-10-04) — en.wikipedia.org
3. Peter Taylor, "What Ever Happened to Those Bridges?", Australian Mathematics Trust,… — web.archive.org
4. J. J. O'Connor and E. F. Robertson, "Leonhard Euler", MacTutor History of Mathematics,… — mathshistory.st-andrews.ac.uk
5. Teo Paoletti, "Leonard Euler's Solution to the Konigsberg Bridge Problem",… — web.archive.org
6. The Euler Archive, "E53: Solutio problematis ad geometriam situs pertinentis",… — scholarlycommons.pacific.edu
7. Wikipedia, "Seven Bridges of Königsberg" (read 2026-10-04) — en.wikipedia.org
8. Carl Hierholzer and Chr. Wiener, "Ueber die Möglichkeit, einen Linienzug ohne… — link.springer.com
9. Wikipedia, "Icosian game" (read 2026-10-04) — en.wikipedia.org
10. J. J. O'Connor and E. F. Robertson, "William Rowan Hamilton", MacTutor History of… — mathshistory.st-andrews.ac.uk
11. The Puzzle Museum (Hordern-Dalgety collection), "Sir William Hamilton's Icosian Game… — puzzlemuseum.com
12. Clay Mathematics Institute, "P vs NP" and "The Millennium Prize Problems" — claymath.org
13. Wikipedia, "Hamiltonian path problem" (read 2026-10-04) — en.wikipedia.org
14. Philip L. Frana and Thomas J. Misa, "An Interview with Edsger W. Dijkstra",… — web.archive.org
15. J. J. O'Connor and E. F. Robertson, "Edsger Wybe Dijkstra", MacTutor History of… — mathshistory.st-andrews.ac.uk
16. E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs", Numerische… — ir.cwi.nl
17. H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner… — arxiv.org
18. P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic… — ai.stanford.edu
19. R. Geisberger, P. Sanders, D. Schultes and D. Delling, "Contraction Hierarchies:… — web.archive.org
20. Grzegorz Czajkowski, "Large-scale graph computing at Google", Google Research blog, 15… — research.google
21. Wikipedia, "Kaliningrad" (read 2026-10-04) — en.wikipedia.org
22. Matthias Stallmann, "The 7/5 Bridges of Koenigsberg/Kaliningrad", North Carolina State… — web.archive.org

Image credits

• Königsberg, engraving by the Merian heirs, c. 1652 · public domain · via Wikimedia Commons
• Leonhard Euler · pastel by Jakob Emanuel Handmann, 1753 · Kunstmuseum Basel · public domain · via Wikimedia Commons
• Euler's Fig. 1 · Commentarii Academiae Scientiarum Petropolitanae vol. 8 (printed 1741) · public domain · scan via M. Behrend

Researched and scripted with AI assistance, fact-checked claim by claim, with synthetic narration and diagrams drawn in code. How we make episodes.