Frontier Science › Mathematics · Feature · Practical STEM, Part 1
Seven bridges, no way across: how Euler turned a city's riddle into the science of networks
Exactly 290 years ago today, Leonhard Euler showed that no one could cross all seven bridges of Königsberg exactly once. His proof gave birth to graph theory — the mathematics behind maps, the internet and even the reading of DNA.
On 26 August 1735, a 28-year-old mathematician presented a short paper to the Academy of Sciences in St Petersburg. Its subject was a puzzle from a Prussian city several hundred kilometres away. Euler was not sure the puzzle was even mathematics. Then he saw what no one else had: the question was not about distance or shape at all. It was about connection.
The riddle of the seven bridges
Königsberg sat on the River Pregel, which flowed around two islands in the heart of the city. Seven bridges tied the four pieces of land together. Locals asked a simple question on their Sunday walks: could you stroll through the city and cross every bridge exactly once? Nobody could find such a route. Nobody could prove that none existed.
Euler’s leap
Euler threw away the map. Each piece of land became a point; each bridge became a line between two points. What remained was a simple diagram — what mathematicians now call a graph.
Then he counted. Every time you walk onto a piece of land, you must also walk off it, so each visit uses two bridges. Any land you pass through must therefore have an even number of bridges. Only the start and the end of the walk may have an odd number.
In Königsberg, all four land areas had an odd number of bridges: the central island had five, and the other three had three each. Four odd points, when a walk allows at most two. The route was impossible — not because nobody had tried hard enough, but because it could not exist.
From riddle to rule
Euler’s insight became a general rule: in any connected network, you can trace every line exactly once only if zero or two points have an odd number of lines. Euler showed why the condition is necessary. More than a century later, in 1873, the German mathematician Carl Hierholzer proved that it is also sufficient. Such routes now carry Euler’s name: Eulerian paths.
Why it matters today
- Routes and deliveries. Snowploughs, street sweepers and postal rounds are planned with a direct descendant of Euler’s question, the “Chinese postman problem”: the shortest route that covers every street at least once.
- Networks. The internet, power grids and airline schedules are all graphs. Engineers study their points and lines to keep them fast and resilient.
- Biology. In 2001, researchers showed that short fragments of DNA can be assembled into a genome by finding an Eulerian path through a graph of overlapping sequences.
- Social connections. Every “people you may know” suggestion is a calculation on a graph of friendships.
The practical lesson
Euler stripped away everything that did not matter — distances, shapes, street names — and kept only the structure. Then he asked what must be true about it. Good engineers, scientists and founders do the same. Once you see a problem’s essential shape, you can often tell at once whether it can be solved — and if it can’t, you stop wasting effort and change the problem instead.
Try it yourself
Draw four dots: a central island, a north bank, a south bank and an east island. Join the island to each bank with two lines, and to the east island with one. Join each bank to the east island with one line. Now add an eighth bridge between any two dots. Can you find a walk that crosses every line exactly once? Count the dots with an odd number of lines first.
Where KATZ begins
The Königsberger Bridges Institute takes its name from this puzzle. KATZ begins here too: with a city, a question, and the conviction that the right way of seeing can turn the impossible into the solved.
Sources: Euler, “Solutio problematis ad geometriam situs pertinentis,” Commentarii academiae scientiarum Petropolitanae 8 (1741), Euler Archive E53 · Hierholzer, Mathematische Annalen 6 (1873) · Pevzner, Tang and Waterman, “An Eulerian path approach to DNA fragment assembly,” PNAS 98 (2001) · Kwan Mei-Ko (1962), the Chinese postman problem · Euler’s letter to Carl Ehler (1736).
How this story was made: drafted by Luise Hönig (Virtual Contributor), completed by Gustav Hohenstein, approved by Yoshihiro Horiuchi, Editor-in-Chief.
How this story was made: drafted by Luise Hönig (Virtual Contributor), completed by Gustav Hohenstein, approved by Yoshihiro Horiuchi, Editor-in-Chief.