Mathematics & Logic · Games, networks & optimization
The seven bridges of Königsberg
Turn a famous walking puzzle into points and lines, then count the bridges at each piece of land to prove the walk impossible without trying a single route.

What you will learn
- Identify what vertices and edges represent in the bridge problem.
- Distinguish crossing every bridge once from visiting every land region once.
- Explain why arrivals and departures pair up at an intermediate vertex.
- Use the odd-vertex condition to rule out the historical seven-bridge route.
Lesson 1 of 4 · 4 min
Turning Königsberg's bridges into dots and lines
In the 1730s the city of Königsberg, in Prussia, had seven bridges over the river Pregel. The river split the city into four land regions, two banks and two islands. People asked whether one walk could cross every bridge exactly once. You could wander inside a region and come back to it later, but you couldn't reuse a bridge.
Nobody had found such a walk, and nobody could show there wasn't one. Leonhard Euler heard about the puzzle and reported that some people denied it could be done, others doubted it, and nobody claimed it could.
You could settle it by trying every possible route. Euler called that difficult and laborious. His 1736 paper took another way. He saw that distances and shapes make no difference. All that counts is which bridge joins which region.
Here's the move. Replace each land region with a point, called a vertex, and each bridge with a connecting line, called an edge. The network you get is called a graph.
Two bridges between the same regions stay two separate edges, because each one has to be crossed. The exact shapes of the islands and the lengths of the bridges don't decide whether this walk exists. Only the pattern of connections does.
A walk that uses every edge once is called an Euler trail, and some sources call it an Euler path. If it ends where it started, it's an Euler circuit.
Neither definition forbids revisiting a vertex. You might reach an island by one bridge, leave by another and come back later by a third. That doesn't break the rule, because no bridge was repeated.
Visiting every land region exactly once would be a different puzzle, about vertices instead of edges. Finding the shortest route would be different again, and it would need the distances our simplified graph threw away.
A useful model keeps what matters for its question and says what it leaves out. Here the question is whether all seven crossings can be made exactly once, with the walk ending either where it began or somewhere else.
Try to recallWhy can an Euler trail revisit the same island without breaking the one-crossing-per-bridge rule?
The rule says each bridge, or edge, must be used exactly once. It doesn't say each land region, or vertex, can only be visited once.
Everything the puzzle needs from Königsberg fits in four points and seven lines. The streets, the distances and the bends of the river are gone, and the question is unchanged. Can one walk use every line exactly once?
Lessons in this topic
Turning Königsberg's bridges into dots and lines
Seven bridges, four pieces of land and a walk nobody in town could find. Strip the map down to points and lines and the puzzle becomes something you can reason about.
Why no walk crosses all seven bridges once
Count the bridges touching each piece of land. Four odd counts prove that Königsberg's walk can't be done, without trying a single route.
What would one new bridge change?
Add a bridge or two to Königsberg and see when the impossible walk becomes possible, as it has in the real city. Then see why the counting test only works on a network that's all in one piece.
The handshake rule that catches a miscounted map
Every bridge has two ends, so the counts at all the land regions add up to twice the number of bridges. Use that to count edges and to spot a map that can't exist.
Three quick stories from this topic
The impossible handshakes
Nine people at a party can't each shake hands with exactly seven of the others
It sounds easy, since each person just skips one other guest. But add up the handshakes all nine people made and you get 63. Every handshake is counted twice, once for each person, so that would mean 31.5 handshakes.
The handshake lemma
In any network, the connection counts of all the points add up to twice the number of connections, because every connection has two ends.
The same rule checks a bridge map
Königsberg's four land regions had 5, 3, 3 and 3 bridge ends. That's 14 ends, so there were seven bridges.
Euler's bridge count
Euler proved Königsberg's seven-bridge walk impossible without trying a single route
A walk that passes through a piece of land uses its bridges in pairs, one to arrive and one to leave. Only the start and the finish can have an odd number. In Königsberg all four land regions did, with 5, 3, 3 and 3.
Only two endpoints can be exceptions
A walk may start at one odd-degree region and finish at another.
The historical network has four
That's why no route uses all seven bridges exactly once, even if the start and finish are allowed to differ.
The walk is possible now
Two bombed bridges turned Euler's impossible Königsberg walk into a possible one
Bombing in World War II destroyed two of the seven bridges. Five remain on the original sites in what is now Kaliningrad, Russia. Only two land regions now touch an odd number of them, so one walk can cross all five, starting on one island and ending on the other.
Euler's answer in 1736
In 1736 Euler showed that no walk can cross each of the seven bridges exactly once, wherever it starts or finishes, and MathWorld calls that result the beginning of graph theory. The seven bridges and four land regions form a multigraph with four nodes and seven edges.
Same city, different graph
For the modern bridges, MathWorld reports, citing J. Kåhre, that there's still no Eulerian cycle but there is an Eulerian path. Every bridge can be crossed once if the walk is allowed to end somewhere other than where it began.
Sources
- Euler Paths and Circuits, Oscar Levin, Discrete Mathematics: An Open Introduction
- Königsberg Bridge Problem : Wolfram MathWorld, Wolfram MathWorld
- Leonhard Euler, “Solution of a problem in the geometry of position”, Michael Behrend
- Seven Bridges of Königsberg, Wikimedia Foundation
- Definitions (Graph Theory), Oscar Levin, Discrete Mathematics: An Open Introduction
- A history of Topology, MacTutor History of Mathematics, University of St Andrews





