KÖNIGSBERG · EAST PRUSSIA · 1736
A parlour puzzle no citizen can solve. Can you cross all seven bridges without crossing any twice? Mathematicians across Europe have tried. All have failed.
Leonhard Euler answers the question by refusing to look at the bridges at all.
Part of Graph Theory: four standalone stories tracing the mathematics of connection.
See all four →Seven bridges, four land masses, and a walk nobody could quite finish.
Königsberg in 1736 was a prosperous merchant city in East Prussia, sitting on both banks of the Pregel river. Two islands sat in the river's middle: Kneiphof, the larger one, home to the cathedral and university, and Lomse, a smaller island to the east. Seven bridges connected these four land masses.
Sunday walks were a local institution. The puzzle became a fixture of Königsberg parlours: could you take a walk through the city that crossed each bridge exactly once, and returned you to where you started? People tried. They tried with string and paper. They tried over dinner and over brandy. Nobody produced such a walk. Nobody could prove one was impossible either.
The puzzle, precisely stated
Starting anywhere in the city, is it possible to take a walk that crosses each of the seven bridges exactly once and returns you to the same place? This is not a riddle. There is no trick wording. It's a genuine question about the geometry of a real city.
Leonhard Euler was not, at first, impressed.
Leonhard Euler was twenty-nine, already famous across European scientific circles, and working at the Imperial Academy of Sciences in St. Petersburg. He was the most prolific mathematician who has ever lived, and he was about to become more so: in a career that spanned five decades he would produce so much original work that publishing the backlog took another forty years after his death.
When the mayor of Danzig, Carl Ehler, wrote to Euler asking about the bridges, Euler's first reaction was dismissive. In a reply, he called the problem “banal”: a parlour game, not real mathematics. Real mathematics, as everyone understood it, meant calculus, differential equations, and the motion of celestial bodies. The shapes of a city were a matter for engineers.
But he kept thinking about it. What caught his attention was not the puzzle itself but the fact that none of his existing tools could touch it. Geometry as the Greeks had built it measured lengths and angles. Algebra counted quantities. The bridges of Königsberg resisted both. The question was about how things connect, and that was a question no one had a language for.
“This question is so banal, but seemed to me worthy of attention, in that neither geometry, nor algebra, nor the art of counting was sufficient to solve it.”
Later that year he wrote up his solution. The paper, Solutio problematis ad geometriam situs pertinentis (“The solution of a problem relating to the geometry of position”) would be published in 1741. It is regarded today as the founding document of graph theory and of topology. Euler himself thought of it as a curiosity.
Everyone was thinking about the bridges. Euler stopped thinking about the bridges.
The obvious approach is to try every possible route through the city and see whether any of them work. With seven bridges there are only a few thousand orderings, few enough for a human to rule out in an afternoon. That's what the citizens had been doing.
Euler made a different move. He noticed that it cannot possibly matter how the bridges are laid out. Whether Krämerbrücke curves gracefully over the Pregel or runs dead straight, whether Kneiphof is large or small, whether the river is fast or slow: none of it changes the answer. What changes the answer is only which land masses are connected to which, and how many times.
So erase the map. Replace each land mass with a dot. Replace each bridge with a line. You are left with a picture containing four dots and seven lines. The city is gone. Only the connections remain. The question that seemed to be about a Prussian city turns out to be about this tiny diagram, and nothing else.
Why this move matters
This is the move that made graph theory a field. Almost every algorithm that follows (Dijkstra's shortest path, Ford-Fulkerson max-flow, PageRank, the BGP routing tables that hold the internet together) inherits Euler's insight. The geography vanishes. Only the structure of connection remains, and that structure is what governs the answer.
Below is Königsberg after Euler has finished with it. Four nodes labelled N, S, K, L. Seven bridges between them. Click any bridge to add or remove it, and watch the puzzle change.
Click a bridge to toggle it. Land masses with an odd number of bridges are highlighted.
Status
No Eulerian walk exists
4 land masses have an odd number of bridges. Euler's rule requires exactly 0 or 2.
Land masses
Euler's rule
A walk that crosses every bridge exactly once exists iff 0 or 2 land masses have an odd number of bridges. A circuit that also returns to start requires 0.
Try it: remove one of the Kneiphof bridges. Suddenly a walk becomes possible, but only if you start at one of the remaining odd-degree land masses. Remove two bridges of the right pair, and you can even return home. The question "is the walk possible?" collapses into a question about the parity of four numbers.
One rule, proved in a few lines, settles every city in the world.
The degree of a node is the number of edges meeting at it. For Königsberg, the four degrees are . The sum of degrees is always twice the number of edges, because every edge has two endpoints.
Now imagine you are walking the graph, crossing every edge exactly once. Consider any node that is not your start or end. Every time you walk into it, you must eventually walk out. The edges pair up. So every intermediate node must have an even number of edges meeting it.
The start and end are the only nodes that can get away with an odd degree. If the walk is a circuit (returning to the starting node), even that exemption disappears, because the start is also the end.
Euler's Theorem (1736)
A connected graph has an Eulerian circuit if and only if every node has even degree. It has an Eulerian path if and only if exactly zero or two nodes have odd degree.
Translated out of the symbols, here is what the theorem says. Stand at every node in turn and count how many edges meet it. Some counts will come out even, some odd. Now tally just the odd ones. If that tally is zero, you can trace the whole figure in one continuous sweep without lifting your pencil, and you will end up back where you started. If the tally is exactly two, you can still trace the whole figure in one sweep, but you must start at one of the two odd-count nodes and finish at the other. Any other tally (one, four, six, seventeen) and the task is flatly impossible.
Why is the rule this clean? Because of the walking-in-walking-out argument above: every node except possibly your start and your end has to have edges that pair up, so its degree has to be even. The odd-degree nodes, if any, are forced to sit at the two ends of your walk. You cannot have more than two of them because you only have one pencil, one start, one end. That is the whole content of the theorem: a global, existence-type question about walks in an arbitrarily complicated graph, reduced to an arithmetic check you can do by counting on your fingers.
Count the bridges at each land mass:
North bank
3
odd
South bank
3
odd
Kneiphof
5
odd
Lomse
3
odd
Four odd-degree nodes. Euler's rule demands zero or two. The Königsberg walk cannot be done, not because nobody has been clever enough, but because the numbers forbid it. This is the first impossibility proof in graph theory: a rigorous argument that no amount of cleverness will solve a problem, because the structure itself forbids the solution.
What Euler quietly invented
The theorem is a small thing. The habit of mind is not. Euler had shown that a physical question could be translated into a purely combinatorial one, solved there, and the answer trusted. Two centuries later, this is how we reason about the internet, logistics networks, molecular chemistry, and the connection patterns in neural networks.
A graph in forty lines. Euler's theorem in four.
An undirected multigraph backed by an adjacency list. Degree falls out of list length. Connectivity falls out of BFS.
from dataclasses import dataclass, field
from collections import defaultdict, deque
@dataclass
class Graph:
"""Undirected multigraph. Parallel edges are preserved."""
_adj: dict[str, list[str]] = field(default_factory=lambda: defaultdict(list))
def add_edge(self, u: str, v: str) -> None:
self._adj[u].append(v)
self._adj[v].append(u)
def degree(self, node: str) -> int:
return len(self._adj[node])
def is_connected(self) -> bool:
if not self._adj: return True
start = next(iter(self._adj))
visited, queue = {start}, deque([start])
while queue:
for v in self._adj[queue.popleft()]:
if v not in visited:
visited.add(v)
queue.append(v)
return len(visited) == len(self._adj)
def odd_degree_nodes(self) -> list[str]:
return [n for n in self._adj if self.degree(n) % 2 == 1]Two predicates for the theorem. Build Königsberg as Euler would have drawn it. Verify the puzzle is impossible.
def has_eulerian_circuit(g: Graph) -> bool:
"""Euler's theorem: connected + every node even-degree."""
return g.is_connected() and len(g.odd_degree_nodes()) == 0
def has_eulerian_path(g: Graph) -> bool:
"""Connected + 0 or 2 odd-degree nodes."""
return g.is_connected() and len(g.odd_degree_nodes()) in (0, 2)
# Königsberg, 1736
g = Graph()
for _ in range(2): g.add_edge("N", "K") # North ↔ Kneiphof × 2
for _ in range(2): g.add_edge("S", "K") # South ↔ Kneiphof × 2
g.add_edge("K", "L") # Kneiphof ↔ Lomse
g.add_edge("N", "L") # North ↔ Lomse
g.add_edge("S", "L") # South ↔ Lomse
print({n: g.degree(n) for n in "NSKL"}) # {'N': 3, 'S': 3, 'K': 5, 'L': 3}
print(has_eulerian_path(g)) # FalseNotebook 06: Königsberg & Euler
Build the graph. Count the degrees. Verify the puzzle is impossible. Then modify the bridges. Which edits make a walk possible? Which make a circuit possible? Work it out and let the code confirm.
notebooks/06_graph_theory_koenigsberg.ipynb → The abstraction became a discipline. The discipline became infrastructure.
Graph theory as a field took shape over the next two centuries: quiet, academic, and largely unnoticed. Gustav Kirchhoff used graphs to analyse electrical circuits in 1845. Arthur Cayley used them to count chemical isomers in 1857. In 1936, the Hungarian mathematician Dénes König wrote the first textbook devoted to the subject, eight years before the Allies landed at Normandy, and two decades before the algorithms that would make graphs indispensable.
Then the applications arrived all at once. The Cold War motivated network-flow theory at RAND. The internet turned every packet into a graph-routing problem. Web search turned every page into a node in a graph with billions of edges. Today, the abstraction Euler invented to dismiss a parlour puzzle is the mathematical substrate of modern infrastructure. You have used it every time you have opened a web browser.
Next story
Shortest paths
Dijkstra's algorithm, and the networks that made it matter.
Then
Flow and cuts
Max-flow, min-cut, and the Cold War study that gave us both.
Finally
Random walks
PageRank built Google this way. Modern LLMs retrieve knowledge this way.
A short, opinionated bibliography. Start with Euler himself.
Leonhard Euler, Solutio problematis ad geometriam situs pertinentis (1741)
The 1736 paper itself, in Euler's Latin and in modern English translations. Shorter than you expect. A lesson in how to write mathematics plainly.
Reinhard Diestel, Graph Theory (Springer, 5th ed. 2017)
The modern standard reference. Free PDF from the author. Start with chapter 1 for a rigorous treatment of what we sketched above.
Robin Wilson, Introduction to Graph Theory (Longman, 5th ed. 2010)
The gentlest introduction to the field. Historical asides on Euler and Königsberg. Accessible to anyone who made it through this lesson.
Alexander Schrijver, On the History of Combinatorial Optimization (till 1960)
Essential if you want to know what actually happened at RAND, what was known during WWII, and what was retroactively attributed. Long, careful, and very fair. Sets up the next three stories in this topic.
Euler dismissed the puzzle as banal. In solving it, he founded two branches of mathematics, and supplied the language for an answer to problems that did not yet exist.
The bridges of Königsberg no longer stand. Two were destroyed in the Second World War, and the city itself was renamed Kaliningrad after it became part of the Soviet Union. The graph, however, is immortal.