Imagine you’re in the 18th-century Prussian city of Königsberg. The city is a beautiful one, built around the river Pregel, which flows around two large islands. To connect these landmasses—the two riverbanks and the two islands—the city has constructed seven distinct bridges.
As a local, a popular brain teaser emerges: Can a person go for a walk through the city, crossing each of the seven bridges exactly once? You can start and end wherever you like.
It sounds simple enough, doesn’t it? For years, the residents of Königsberg tried and failed, walking countless paths, but no one could seem to solve it. Was it even possible? The puzzle became so famous that it eventually reached the ears of one of history’s greatest mathematicians, Leonhard Euler.
Euler’s Brilliant Insight: The Map Doesn’t Matter!
When Euler tackled the problem in 1736, he had a revolutionary “Aha!” moment. He realized that the exact shape of the islands, the length of the bridges, and the specific path you walked on land were all irrelevant distractions. The only thing that mattered was the relationship between the landmasses and the bridges.
He did something brilliant: he abstracted the problem.
- He represented each of the four landmasses (the two riverbanks and the two islands) as a simple dot, which we now call a node or vertex.
- He represented each of the seven bridges as a line connecting the corresponding dots. These are now called edges.
His complex city map was suddenly transformed into a simple network diagram, something like this: One dot for the North Bank, one for the South Bank, one for the East Island, and one for the West Island, with lines (bridges) connecting them.
The Solution and a New Set of Rules
By looking at this simplified network, Euler could analyze the problem logically instead of geographically. He noticed that to walk a path crossing each bridge exactly once, your journey must have a start and an end. For any landmass (node) that is not the start or the end of your journey, you must arrive by one bridge and leave by another. This means that every “intermediate” node must have an even number of bridges connected to it.
He deduced the following rules:
- If a network has zero nodes with an odd number of connections, you can start anywhere, cross every bridge once, and end up back where you started (an “Eulerian circuit”).
- If a network has exactly two nodes with an odd number of connections, you can still cross every bridge once, but you must start at one of the odd nodes and end at the other (an “Eulerian path”).
- If a network has more than two nodes with an odd number of connections, the problem is impossible.
When Euler looked at his diagram for Königsberg, he found that all four landmasses had an odd number of bridges connected to them. With four odd nodes, the puzzle was unsolvable!
The Birth of Graph Theory
Euler’s solution was far more important than just solving a local brain teaser. By focusing on the properties of nodes and edges, he laid the foundation for a completely new field of mathematics: Graph Theory, a branch of topology.
Graph Theory is the study of networks—of connections. And it turns out, this “simple” idea powers our modern world in countless ways:
- GPS & Navigation: Google Maps uses graph theory to find the shortest path (in distance or time) between two locations (nodes).
- Social Networks: Facebook, LinkedIn, and X are giant graphs where you are a node, and your friendships/connections are the edges.
- The Internet: The entire internet is a graph of computers and routers connected by data links.
- Airline Routes & Logistics: Planning the most efficient flight paths or delivery routes is a complex graph theory problem.
All of this from a simple, centuries-old puzzle about taking a walk. It’s a perfect example of how curiosity and a new perspective can change the world!
