During the 18th century the denizens of the Prussian city of Königsberg wrestled with a puzzle: How could they find a walking path through the city that crossed each of its storied seven bridges exactly once?
The bridges spanned a river containing two large islands. No matter how much they strategized their routes, they couldn’t avoid repeating a bridge.
The problem stymied local thinkers, who eventually wrote a letter to famed mathematician Leonhard Euler (pronounced “oiler”) begging him to lay their curiosity to rest. Euler responded dismissively, claiming the problem had “little relationship to mathematics.” In a way, he was right, because the relevant math hadn’t been invented yet. Despite his initial demurral, Euler did end up solving the puzzle of the seven bridges of Königsberg, unaware that in the process he had birthed two new branches of math.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
The Prussian city of Königsberg, now Kaliningrad in Russia, in the Middle Ages. The 18th-century city map is a digitally enhanced reproduction that was modified to highlight the river and bridges.
Credit: Alamy Stock Photo (map); Amanda Montañez (highlighting)
Say you were a resident of Königsberg. Looking at the map above could you design a path that traverses every bridge once? You’ll have to think like a mathematician. The first hurdle in wrangling any math problem is to strip away extraneous information until only the essential elements remain, a process called abstraction. Many features of the map don’t affect the question at hand. The lengths of the bridges, the sizes of the landmasses, even the geographical orientation of the land and bridges can all be discarded. All that matters is which pieces of land connect to which other ones and how many times. Now we can create a much simpler diagram consisting only of circles and lines to represent land and bridges, respectively.
Credit: Alamy Stock Photo (map); Amanda Montañez (highlighting and diagram)
Modern math parlance calls this a “graph,” not to be confused with other unrelated mathematical graphs like plots in the x-y plane or statistical visualizations like bar graphs. Perhaps “network” would have been a better term to avoid any confusion. We call the circles “vertices” and the lines “edges.” Today graph theory is a major area of math and computer science with wide-ranging applications. Graphs don’t have to represent land and bridges. They can represent social networks, protein interactions, state borders, neural networks, the World Wide Web or any other data involving pairwise relationships.
Abstraction allows mathematicians to translate a highly specific problem about a particular arrangement of bridges in an old city to a general problem about all graphs. Given a graph with any number of vertices and edges, is there a path that traverses every edge exactly once? It turns out that an amazingly simple test can answer this for any graph: For every vertex (landmass in our current puzzle), count the number of edges (bridges) emanating from it. If all of those counts are even numbers, or if all but two of them are even, then the path exists; otherwise, the path is impossible.
Let’s explore the reasoning. Imagine a path through a graph that crosses each edge once. Consider a vertex in the middle of that path (not the starting or ending vertex). If that vertex has many edges, then your path will visit it multiple times, but every time you enter the vertex, you must also exit it via a different edge. So each time a vertex in the middle of the path gets visited, two edges get visited. That only works if every vertex in the middle of the path has an even number of edges. The start and end of the path are the only exceptions, because the starting vertex doesn’t have to be entered, and the ending vertex doesn’t have to be exited. So if we have exactly two vertices with an odd number of edges, then our path is possible if you start and end at those vertices. If every vertex has an even number of edges, then there will be a path that starts and ends at the same vertex forming a loop.
This argument is considered the first result in graph theory, and paths through graphs that visit every edge once are now called Eulerian paths. Technically Euler’s argument describes only the conditions that make an Eulerian path impossible, and the proof that such a path always exists under these conditions came later. Applying what we’ve learned to the bridges of Königsberg, we see that all four vertices have an odd number of edges emanating from them, meaning, alas, the Prussian amblers searched in vain.
Here’s a peculiar side note. Finding a path through a graph that visits every vertex (the land rather than the bridges in our example) exactly once sounds like a closely related problem, but is actually an entirely different beast. Though a simple test can determine whether a graph contains an Eulerian path, we don’t know any general efficient procedure for this vertex-focused variant. This variant is called the Hamiltonian path problem, and it belongs to a class of problems widely believed to be computationally intractable.
Although Euler initially sneered at the bridge problem, he was ultimately drawn in by his inability to solve it with his usual tool kit. He wrote to a friend: “This question is so banal, but seemed to me worthy of attention in that neither geometry, nor algebra, nor even the art of counting was sufficient to solve it.” At the time, geometry concerned quantitative notions like distance, angle and area. But while the bridge problem appeared geometric in nature, it didn’t ask for any kind of measurement. The problem required a new abstraction that ignored traditional geometric quantities, while respecting the pairwise connections at the heart of the question.
The idea to reduce the map of Königsberg to a bare-bones graph might seem obvious in retrospect, but many of the best abstractions do. The history of math tells the story of the power of abstraction. If ancient mathematical minds had quantitative questions about oranges, pearls or even the Earth, they could develop bespoke language and techniques for tackling each new challenge. But the endeavor becomes so much easier and clearer once one recognizes that these disparate-seeming objects all instantiate the same higher-order entity: a sphere. Giving the abstraction a name and a definition allows people who have never even met to build on each other’s work without reinventing the wheel.
Euler’s paper not only launched the field of graph theory, but it also sowed the seeds for another major branch of math called topology. Topology refers to the study of geometric properties that persist even when we stretch, compress or deform objects as though they were made of highly elastic rubber. So while one level of abstraction took us from real-world objects such as oranges, mountains and dice to their shapes (spheres, pyramids and cubes), topology introduces a second level of abstraction in which we view spheres, pyramids and cubes as instantiations of some even higher-order entity. Topologists view these solids as equivalent because they can each be molded into the others in a rubbery world, unlike a doughnut, which would maintain a hole no matter how you stretched it.
By abstracting away the quantitative particulars in the map of Königsberg, Euler opened the door to a new kind of geometric thinking, unmoored from the quantitative particulars of distance and angle that had dominated the subject for millennia. Graph theory and topology continue to yield new mathematical insights today, and we have a bygone civilization of saunterers to thank.