Euler's seven bridges of Königsberg: how graph theory began
Königsberg's puzzle: cross all seven bridges once each. Euler proved it impossible with just dots and lines, founding what now runs maps and genomics.

Mục lục
A Sunday stroll
In the 18th century, Königsberg was a prosperous Prussian port city. The river Pregel flowed through the middle of town, wrapping around two islands and splitting the land into four regions: the north bank, the south bank, the island of Kneiphof in the middle, and an island to the east. Seven bridges connected those regions.
The townspeople passed around a puzzle. Is there a way to take a walk across all seven bridges, each exactly once, without wading through the river and without crossing any bridge twice?
It sounds simple. You can try it right now on Figure 1 below: put your finger on any piece of land and start walking. Very quickly you will find yourself stuck with one bridge left that you can no longer reach.
Some said the puzzle had no solution. But nobody could prove it. Maybe nobody had tried enough routes? Seven bridges give thousands of different orders, and nobody wanted to try them all.
In 1736, the mathematician Leonhard Euler gave a definitive answer: impossible. His reason was so short it could be explained to a primary-school child. And on the way to that reason, he founded a new branch of mathematics that today runs inside the map app on your phone.
This is the second article in a series on mathematicians. Each one tells the story of one person and one moment in their life.
“Little relationship to mathematics”
Euler was not yet 30, working at the Academy of Sciences in Saint Petersburg, Russia. Born in Basel, Switzerland, he would become one of the most prolific mathematicians in history. His complete works run to more than 70 volumes, much of it written as his eyesight failed, and many works dictated to others when he was almost completely blind.
The bridge problem reached Euler by letter. Carl Ehler, mayor of the nearby city of Danzig, wrote asking him to solve the puzzle, on behalf of a friend who was a mathematics professor in Danzig. In his reply of 3 April 1736, Euler sounded rather unimpressed[2]:
Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone.
Euler was wrong about exactly one thing: this was mathematics, just a kind of mathematics that had no name yet. A few months earlier he had presented his solution to the Academy. The paper, in Latin, was titled Solution of a problem relating to the geometry of position, and appeared in the Academy’s proceedings for 1736, although that volume was only actually published in 1741[1].
“Geometry of position” (geometria situs) was a name Leibniz had used earlier for a kind of geometry he only vaguely imagined: a geometry that ignores distances and angles and cares only about what connects to what. Euler realized the bridge problem belonged to exactly that kind.
Throwing away the map
Euler’s most important step was to throw away almost everything on the map.
The shape of the island does not matter. The length of a bridge does not matter. Whether we walk fast or slow, or turn left or right on a piece of land, does not matter either. The only thing that affects the answer is: which piece of land connects to which, by how many bridges.
So shrink each piece of land to a dot, and draw each bridge as a line joining two dots. The complicated map of Königsberg becomes four dots and seven lines:
- the north bank joins Kneiphof by two bridges;
- the south bank joins Kneiphof by two bridges;
- the north bank, the south bank and Kneiphof each have one bridge to the east island.
Today, a drawing of dots and lines like this is called a graph. The dots are vertices, the lines are edges. “Graph” here does not mean the graph of a function from school, but a network. Euler did not use that word, nor did he draw pictures this way. He reasoned with letters and tallies. But the idea of reducing the world to a network was his, and it is the starting point of graph theory.
An argument that only needs counting
Now look at any piece of land we pass through on the walk, that is, neither the starting point nor the end. Each time we visit it, we use exactly two bridges: one to get in, one to get out. Visit it three times and we use six bridges. Since each bridge may be used only once, the total number of bridges touching that land must be an even number.
The number of bridges touching a piece of land is called the degree of that vertex. The argument says: on a walk crossing each bridge exactly once, every piece of land in the middle of the journey must have even degree. Only the start and the end may have odd degree, because there one bridge “goes out” without “coming in”, or the other way round.
So count the degrees of Königsberg:
| Land mass | Bridges (degree) |
|---|---|
| Kneiphof | 5 |
| North bank | 3 |
| South bank | 3 |
| East island | 3 |
All four pieces of land have odd degree. But a walk has only one start and one end, so at most two odd pieces of land. With four odd ones, at least two of them must lie “in the middle” of the journey while having odd degree, which cannot happen. The puzzle has no solution. No route ever needs to be tried.
Euler stated the general conclusion for every network of bridges, in every city:
- If there are more than two pieces of land of odd degree: there is no walk.
- If there are exactly two pieces of land of odd degree: a walk exists, but it must start at one odd piece and end at the other.
- If there are no pieces of land of odd degree: a walk exists, and it can return to where it started.
Euler clearly proved the “impossible” direction: the even-degree condition is necessary. The converse, that whenever the condition holds a walk is guaranteed to exist, he asserted but did not fully prove. It took more than a century before the German mathematician Carl Hierholzer proved it completely. His work was published in 1873, after he passed away. Today, a walk that crosses each edge exactly once is called an Eulerian path.

The eighth bridge
Euler’s rule also tells you how to fix the city. Just build one more bridge straight from the north bank to the south bank (right side of Figure 1): the north and south banks go up to degree 4, even; only Kneiphof and the east island stay odd. By rule 2, there is now a walk across all eight bridges, starting at one island and ending at the other. For example:
Kneiphof → east island → south bank → north bank → Kneiphof → south bank → Kneiphof → north bank → east island.
Count again: eight steps, eight bridges, each exactly once.
Königsberg was in fact “fixed”, but not with a new bridge. In 1944 the city was heavily bombed in the Second World War, and two of the seven bridges were destroyed. After the war the city became part of the Soviet Union and was renamed Kaliningrad; it is now a Russian territory. Two more of the old bridges were later demolished. Today that stretch of river has five bridges, only two of them from Euler’s time. With those five bridges, only two pieces of land have odd degree, so crossing each bridge exactly once has become possible. The catch is that the walk must start on one island and end on the other, which is inconvenient for tourists who want to get back to their hotel[5].
From a puzzle to a branch of mathematics
For nearly two centuries, Euler’s idea lived mostly in recreational puzzles. Many of us met one as children: draw a figure in one stroke, without lifting the pen or retracing any line. A house with a pointed roof and two diagonals can be drawn in one stroke, but you must start at a bottom corner. A rectangle with its two diagonals, which looks simpler, cannot be drawn at all.
That is exactly the bridge problem: intersections are vertices, strokes are edges. Count the intersections touched by an odd number of strokes. Zero, and you can draw it and end where you began. Two, and you can draw it, but you must start at an odd point. More than two, and don’t bother trying.
In the 20th century, as people began building huge networks (railways, telephones, computers), graph theory suddenly became one of the most useful branches of mathematics.
Where is the idea today?
Garbage trucks, street sweepers and postmen
A street sweeper must cover every street in its area, then return to the depot. This is almost exactly Euler’s question, except that a street may be driven twice, but as few times as possible, because every kilometer costs fuel and time.
In the early 1960s, the Chinese mathematician Kwan Mei-Ko posed this problem for a postman. It still bears the name Chinese postman problem. The solution follows directly from Euler’s rule: find the intersections of odd degree, pair them up so the total distance between paired intersections is as short as possible, and treat those connecting stretches as “driven twice”. Once every vertex has even degree, there is a closed tour covering every street. Cities use this approach to plan routes for garbage collection, snow plowing and even pipe inspection.
Navigation maps
When you ask a map app for the fastest way home, it does not see the map the way you do. It sees it exactly the way Euler saw Königsberg: every intersection is a vertex, every stretch of road an edge, plus a number for the time it takes to cross that stretch. “Which way is fastest?” becomes a question about the shortest path in a graph. In 1959, the computer scientist Edsger Dijkstra published an algorithm for that problem. Improved versions of it are still the foundation of route planning today.
Reassembling the genome
A gene sequencer cannot read an entire DNA strand billions of characters long. It cuts the DNA into millions of short pieces and reads each one, and then a computer must reassemble the pieces in the right order, like a giant jigsaw puzzle where many pieces look identical.
In 2001, Pavel Pevzner, Haixu Tang and Michael Waterman proposed a new way of looking at it: turn fragment assembly into finding an Eulerian path in a graph built from short stretches of DNA[4]. Instead of trying to fit every pair of pieces together, which is extremely slow, the computer only needs to find a walk crossing each edge exactly once, precisely the kind of problem Euler showed how to recognize and Hierholzer showed how to solve. Most modern genome assembly software is built on this idea.
From a puzzle about a walk to the human genome: nearly three centuries apart, but the core idea is unchanged. Drop the details that don’t matter, keep what connects to what, then count.
Walk the bridges yourself
The Python below does two things. It counts the degree of each piece of land, then uses Hierholzer’s algorithm to find a walk crossing each bridge exactly once, if there is one. It also draws Figure 1 above. All you need is matplotlib.
from collections import Counter
import matplotlib.pyplot as pltfrom matplotlib.patches import FancyArrowPatch
plt.rcParams.update({"figure.facecolor": "#16181c", "text.color": "#d4d7dc", "font.size": 12})
# Four land masses: North (N), South (S), Kneiphof island (K), East island (E). Each bridge is an edge.BRIDGES = [("N", "K"), ("N", "K"), ("S", "K"), ("S", "K"), ("N", "E"), ("S", "E"), ("K", "E")]
def degrees(edges): """Number of bridges touching each land mass (the degree of the vertex).""" return Counter(v for edge in edges for v in edge)
def euler_path(edges): """Hierholzer's algorithm: returns a walk crossing each bridge exactly once, or None.""" deg = degrees(edges) odd = [v for v in deg if deg[v] % 2 == 1] if len(odd) not in (0, 2): return None # Euler's condition: there must be 0 or 2 land masses of odd degree. adj = {v: [] for v in deg} for i, (u, v) in enumerate(edges): adj[u].append((v, i)) adj[v].append((u, i)) used, stack, path = set(), [odd[0] if odd else edges[0][0]], [] while stack: v = stack[-1] while adj[v] and adj[v][-1][1] in used: adj[v].pop() if adj[v]: w, i = adj[v].pop() used.add(i) stack.append(w) else: path.append(stack.pop()) return path[::-1]
print("Degrees in 1736:", dict(degrees(BRIDGES)))print("Walk in 1736:", euler_path(BRIDGES))EIGHT = BRIDGES + [("N", "S")] # add one bridge straight from the north bank to the south bankprint("Degrees with an 8th bridge:", dict(degrees(EIGHT)))print("Walk with 8 bridges:", " → ".join(euler_path(EIGHT)))
# Draw two graphs: 7 bridges (no walk) and 8 bridges (a walk exists).POS = {"N": (0, 1.6), "S": (0, -1.6), "K": (-1.2, 0), "E": (1.8, 0)}NAME = {"N": "north bank", "S": "south bank", "K": "Kneiphof\nisland", "E": "east\nisland"}LABEL = {"N": (0, 0.45), "S": (0, -0.45), "K": (-1.0, 0), "E": (1.05, 0)}fig, axes = plt.subplots(1, 2, figsize=(12, 5.6))for ax, edges, title in [(axes[0], BRIDGES, "1736: 7 bridges, all 4 land masses odd → no walk"), (axes[1], EIGHT, "An 8th bridge: only 2 odd land masses → a walk exists")]: seen = Counter() for u, v in edges: key = tuple(sorted((u, v))) k = seen[key] seen[key] += 1 rad = [0, 0.35, -0.35][k] if key in {("K", "N"), ("K", "S")} else 0 ax.add_patch(FancyArrowPatch(POS[u], POS[v], connectionstyle=f"arc3,rad={rad}", arrowstyle="-", color="#d2b48c" if key == ("N", "S") else "#a4a9b2", lw=2.5, shrinkA=28, shrinkB=28)) deg = degrees(edges) for v, (x, y) in POS.items(): odd = deg[v] % 2 == 1 ax.scatter([x], [y], s=1600, color="#16181c", edgecolors="#e8b05a" if odd else "#8fa9c9", linewidths=3, zorder=3) ax.text(x, y, str(deg[v]), ha="center", va="center", fontsize=18, zorder=4) ax.text(x + LABEL[v][0], y + LABEL[v][1], NAME[v], ha="center", va="center", fontsize=11, color="#a4a9b2") ax.set_title(title, color="#d4d7dc", fontsize=12) ax.set_xlim(-2.6, 3.2) ax.set_ylim(-2.3, 2.3) ax.set_aspect("equal") ax.axis("off")fig.savefig("bridges-en.png", dpi=150, bbox_inches="tight")Degrees in 1736: {'N': 3, 'K': 5, 'S': 3, 'E': 3}Walk in 1736: NoneDegrees with an 8th bridge: {'N': 4, 'K': 5, 'S': 4, 'E': 3}Walk with 8 bridges: K → E → S → N → K → S → K → N → EHierholzer’s algorithm has one neat idea: keep crossing any unused bridge until you get stuck. When stuck, back up to the nearest piece of land that still has an unused bridge, walk a small loop from there, and “splice” that loop into the journey. Try adding or removing bridges in the BRIDGES list to see when a walk appears and disappears.
Back to Königsberg
The Königsberg puzzle has no solution, and the reason fits in one sentence: each time you pass through a piece of land you use two bridges, so land in the middle of the journey must have an even number of bridges, and Königsberg has four odd ones.
Euler thought his solution “bears little relationship to mathematics”. In fact he had just done one of the most mathematical things possible: looking past every surface detail to see the structure underneath. Drop shape, distance and color, keep only the dots and the lines. Three centuries later, those same dots and lines guide you home every evening.
The previous article in this series is about Pascal, Fermat and the unfinished game. The next is about Gauss and an asteroid lost in the glare of the Sun.
Tài liệu tham khảo
- [1]Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 8 (1736, printed 1741), 128–140, 1736.
- [2]Horst Sachs, Michael Stiebitz and Robin J. Wilson. An historical note: Euler's Königsberg letters. Journal of Graph Theory, 12(1), 133–139, 1988.
- [3]Teo Paoletti. Leonard Euler's Solution to the Königsberg Bridge Problem. MAA Convergence.
- [4]Pavel A. Pevzner, Haixu Tang and Michael S. Waterman. An Eulerian path approach to DNA fragment assembly. PNAS, 98(17), 9748–9753, 2001.
- [5]Seven Bridges of Königsberg. Wikipedia.


