Euler's Königsberg Bridges: The Birth of Graph Theory

In the early 18th century, the city of Königsberg (modern-day Kaliningrad) presented its citizens with a seemingly simple recreational puzzle: Could one walk through the city crossing each of its seven famous bridges exactly once and return to the starting point? The answer, published by Swiss mathematician Leonhard Euler in 1736, did not just solve a local curiosity—it fundamentally reshaped mathematics.

Euler's elegant proof introduced a new way of representing problems abstractly, giving birth to graph theory and laying the groundwork for topology, network science, and modern computer algorithms. Today, the principles he discovered power everything from GPS routing to social network analysis.

The Problem of the Seven Bridges

Königsberg was built around the Pregel River, which split into two branches around an island named Kneiphof. The city was connected by seven bridges, linking the island to the north and south banks, and the two banks to each other. Citizens wondered whether a continuous walk existed that would traverse every bridge exactly once.

"The problem is to determine whether there is a route that allows one to cross each bridge exactly once, and if so, to find it." — Leonhard Euler, Solutio problematis ad geometriam continuam pertinentis (1736)

For years, locals attempted the walk experimentally, always failing. Mathematicians of the era approached it as a geometry or algebra problem, drawing maps and writing equations. None succeeded—until Euler changed the perspective entirely.

Euler's Brilliant Abstraction

Rather than measuring distances or angles, Euler asked a more fundamental question: What structural properties of the network determine whether such a walk is possible? He stripped away the physical details of the river, landmasses, and bridge widths, reducing the city to a mathematical model.

Euler represented each landmass as a vertex (or node) and each bridge as an edge connecting two vertices. This abstraction created the first mathematical graph. He then analyzed the degree of each vertex—the number of edges connected to it—and discovered a decisive pattern.

Foundations of Graph Theory

Euler proved that for a continuous walk traversing every edge exactly once to exist, the graph must satisfy a strict condition: at most two vertices can have an odd degree. If exactly two vertices have odd degrees, the walk must start at one and end at the other. If zero vertices have odd degrees, the walk can start and end at the same point (forming a closed loop).

Applying this to Königsberg, Euler found that all four landmasses had odd degrees (5, 3, 3, 3). Since more than two vertices were odd, he conclusively proved the walk was mathematically impossible. The local puzzle was resolved not by trial and error, but by structural analysis.

Eulerian Paths & Circuits

Formalizing his findings, Euler established two fundamental theorems that remain central to graph theory today:

1. Eulerian Path

A graph contains an Eulerian path (traversing every edge exactly once) if and only if it is connected and has exactly 0 or 2 vertices of odd degree. The path must begin at an odd-degree vertex and end at the other.

2. Eulerian Circuit

A graph contains an Eulerian circuit (closed loop returning to the start) if and only if it is connected and every vertex has an even degree.

These conditions are necessary and sufficient. They transformed a recreational puzzle into a rigorous mathematical framework, enabling the analysis of networks of any complexity.

Legacy & Modern Applications

Euler's 1736 paper, Solutio problematis ad geometriam continuam pertinentis, is widely regarded as the first published work in graph theory and topology. Its impact extends far beyond academic mathematics:

• Computer Science: Eulerian paths optimize route planning, circuit board design, and DNA sequencing assembly.
• Network Theory: Social media connections, the internet backbone, and power grids are modeled as graphs to study resilience and information flow.
• Operations Research: Logistics companies use graph algorithms to minimize delivery routes and fuel consumption.
• Topology: Euler's shift from geometric measurements to connectivity properties laid the foundation for modern topology, studying properties preserved under continuous deformation.

The original seven bridges were destroyed during World War II, and Königsberg's layout changed dramatically. Yet the mathematical structure Euler uncovered remains untouched by time. Every time a navigation app calculates a route, or a researcher maps protein interactions, Euler's abstraction continues to work.