Mathematics
The Seven Bridges of Königsberg Problem
Quick fact
Leonhard Euler's 1736 solution to the Königsberg bridge problem is widely considered the first theorem of graph theory, and his method of abstracting landmasses as points and bridges as lines laid the foundation for all modern network analysis.
Why this is interesting
Imagine trying to take a stroll through your city, crossing every bridge exactly once, without ever repeating one. In the old Prussian city of Königsberg, this simple puzzle stumped locals for years—until a mathematician turned it into the birth of an entire branch of science.
Read the full explanation
Understanding The Seven Bridges of Königsberg Problem
Let's step into Königsberg, a city with two large islands in the Pregel River. The four land areas—the north bank, the south bank, and the two islands—were connected by seven bridges. The citizens' challenge: find a walking route that crosses each bridge exactly once and returns to the starting point. They suspected it was impossible, but no one could prove it. Euler took a different approach: he stripped away the geography. He represented each landmass as a circle (a 'vertex') and each bridge as a line (an 'edge') connecting two circles. Suddenly, the puzzle became a simple diagram: four dots and seven lines. Now, the question is: can you trace this drawing with a pencil, never lifting the pen, and never retracing an edge? Euler noticed that when you enter a landmass via one bridge, you must leave via a different one—unless it's your start or end. So, for a route that returns to the start (an Eulerian circuit), every landmass must have an even number of bridges. For a route that starts and ends at different places (an Eulerian path), exactly two landmasses may have an odd number of bridges. In Königsberg, all four vertices had an odd degree (3, 3, 3, and 5). This made the walk impossible, and Euler proved it.
A deeper explanation
The underlying principle is that the structure of a network—not its physical layout—determines what routes are possible. By abstracting landmasses and bridges into a graph, Euler showed that the existence of a path using every edge exactly once depends solely on the degree of each vertex (the number of edges incident to it). This insight is remarkably general and has become the foundation of graph theory. A graph with exactly zero or two vertices of odd degree allows an Eulerian trail; if there are none, the trail is a closed circuit. More than two odd-degree vertices make it impossible. This simple rule is a cornerstone of network analysis and leads to numerous applications: designing postal delivery routes, planning snowplow routes, optimizing garbage collection, and even analyzing DNA sequencing. The Königsberg problem, though a puzzle, elegantly demonstrates the power of abstraction and proof, launching a field that is now central to computer science, operations research, and biology.