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.

4 short lessons · about 17 minutes · 6 sources · updated November 2026

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

Before you readEuler studied the seven bridges of Königsberg and wondered about a walk over each one exactly once. Which detail of the city's map did he find mattered for the puzzle?

Correct.Not quite. The answer is Which region each bridge joins.

Only which bridge joins which region mattered. Distances and shapes made no difference, and this lesson shows how to turn the map 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.

Check yourselfWhen you turn the Königsberg map into a graph, what should happen to two separate bridges that join the same pair of land regions?

Correct.Not quite. The answer is Draw two edges because each bridge must be crossed once.

Each edge stands for one bridge, and both bridges have to be crossed. Merging them into one edge would drop a required crossing and change the task.

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

  1. 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.

    Essentials · 4 min

  2. 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.

    Essentials · 4 min

  3. 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.

    Deeper · 4 min

  4. 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.

    Deeper · 5 min

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

This topic is part of From everyday numbers to proof, a guided path through related topics.

  • Why the shortest delivery route is so hard to find

    Ask for a route that visits every place once, instead of every road once, and the easy test disappears. The number of possible tours outruns any computer, which is why real route planners settle for good enough.

    4 lessons · 22 min

  • Game theory and the prisoner's dilemma

    Game theory studies choices whose results depend on what others choose. See how two prisoners acting sensibly both end up worse off, what a Nash equilibrium is, and why repeating the game can make cooperation pay.

    4 lessons · 16 min

  • Permutations and combinations

    Count possibilities without listing them. Learn when to multiply choices, when order matters and when it doesn't, and work out why a 6-from-49 lottery ticket has about a 1 in 14 million chance.

    4 lessons · 16 min

  • Percentages and why the base matters

    See why a 20% fall takes a 25% rise to undo, why 5% to 10% is both five points and a doubling, and why you can't average two percentages.

    4 lessons · 21 min

  • When the average is the wrong summary

    When one number stands in for a whole set, which number you pick changes the story. Mean, median and mode tend to pull apart when the shape is lopsided.

    4 lessons · 20 min

  • Fractions and decimals

    A fraction is a number, a division and a share all at once. See why adding needs a common denominator and multiplying doesn't, and why some fractions become decimals that never end.

    4 lessons · 16 min

All mathematics & logic topics · Take the quiz