On Sunday afternoons in the early eighteenth century, the citizens of Königsberg liked to stroll. Their Prussian port city straddled the River Pregel, which split around two islands and was crossed by seven bridges linking the islands to each other and to the banks on either side. Somewhere along the way a parlour puzzle took hold: could a walker make a circuit of the city crossing every one of the seven bridges exactly once? Nobody could manage it, and nobody could quite say why. It turned out to be the founding problem of an entire branch of mathematics.
The question reached Leonhard Euler, the Swiss mathematician then working at the Academy of Sciences in St Petersburg, and his first reaction was faint disdain: he wrote to a colleague that the problem had "little relationship to mathematics". But something in it nagged at him. Geometry as then understood was about lengths, angles and areas, and the bridge problem involved none of them — it did not matter how long the bridges were or how the streets curved, only which pieces of land were connected to which. Euler recognised this as a specimen of what Leibniz had vaguely called geometria situs, the "geometry of position", a subject that at that point did not really exist. In 1736 he wrote it into existence, presenting his solution to the St Petersburg Academy in a paper whose Latin title translates as "The solution of a problem relating to the geometry of position".
Euler's beautiful shortcut
Euler's insight was to throw the map away. Shrink each land mass — the north bank, the south bank, and the two islands — to a featureless point, and represent each bridge as a line joining two points. All that remains is a network: four dots, seven lines. In modern language, a graph, with vertices and edges. Then comes the argument, which is short enough to fit in a pub anecdote. Every time your walk passes through a land mass, you use up two bridges — one in, one out. So any land mass that is not the start or the finish of the walk must have an even number of bridges touching it. At most two places — the two ends of the walk — may have an odd number. Now count Königsberg: one island has five bridges, and the other three land masses have three each. Four odd numbers. The stroll is impossible, and no amount of Sunday-afternoon ingenuity was ever going to find it.
The power of the result is its generality: it settles every such puzzle, for any city, in one stroke. A network can be traced in a single walk — an Eulerian path, as it is now called — precisely when it is connected and has zero or two vertices of odd degree; with zero, the walk can return to its start, giving an Eulerian circuit. The dots-and-lines abstraction became graph theory, the mathematics of networks, and the habit of ignoring distances in favour of connections helped seed topology. Railway maps, molecule diagrams, social networks and the London Underground map all live in the world Euler sketched to dispose of a walking puzzle.
And yes — the bin lorry. The flip side of Euler's problem asks: if a perfect once-over stroll is impossible, what is the shortest route that covers every street at least once? Posed by the Chinese mathematician Mei-Ko Kwan in 1962, it is known as the Chinese postman problem, and it is precisely the mathematics of refuse collection, postal delivery, gritting lorries and street-sweeping. Every council routing its fleet down every road with minimal doubling-back is quietly solving a descendant of the Königsberg puzzle.
What happened to the bridges
History was unkind to the props. Königsberg — birthplace of Immanuel Kant, who was born there in 1724, twelve years before Euler's paper — was devastated by British bombing in 1944 and taken by the Soviet army in 1945. The city became Kaliningrad, capital of a Russian exclave wedged between Poland and Lithuania on the Baltic. Two of the seven bridges did not survive the war, and two more were later demolished and replaced by a modern flyover. Five crossings stand on the historic sites today, and puzzle-minded visitors have noted the irony: with five bridges, an Euler-style walk is at last possible — though only if you are willing to start and finish in different places.
Euler himself scarcely paused: over a career split between St Petersburg and Berlin he produced more mathematics than almost anyone in history, working on even after going nearly blind. The bridge paper was a sliver of that output, and graph theory lay largely dormant for over a century afterwards. But origins matter, and this one is unusually pure: no application, no patron, no prize — just a city, a river, seven bridges and the itch of an unanswered question. The next time a delivery van threads your street exactly once, somewhere in the software a ghost of Königsberg is out for its Sunday walk.
Quiz nuggets
- Leonhard Euler solved the Seven Bridges of Königsberg problem in 1736, in a paper presented to the St Petersburg Academy — the founding result of graph theory.
- Euler proved the walk impossible because all four of Königsberg's land masses touched an odd number of bridges; a single-pass walk allows at most two odd-degree vertices.
- The Chinese postman problem — finding the shortest route covering every street — was posed by Mei-Ko Kwan in 1962 and underpins bin-lorry and postal routing.
- Königsberg, birthplace of the philosopher Immanuel Kant in 1724, is now Kaliningrad, a Russian exclave between Poland and Lithuania.
- A walk that crosses every edge of a network exactly once is called an Eulerian path; if it returns to its starting point, an Eulerian circuit.