Can you cross every bridge exactly once?
More than 300 years ago, the city of Königsberg was divided by a river into four areas of land, connected by seven bridges.
People wondered whether it was possible to take a walk through the city that crossed every bridge exactly once.
You may start anywhere and finish anywhere — but you cannot cross any bridge twice.
Challenge: Can you find such a route? Try tracing a route with your finger or sketching one on paper. Remember: every bridge must be crossed exactly once.
Try it yourself. Choose a starting area of land, then click the bridges in the order you want to cross them. Can you cross all seven bridges exactly once?
💡
Reveal hint
Hint: The exact shapes and positions of the land don’t matter.
What if you replaced each area of land with a vertex, and each bridge with an edge?
Turn the city into a graph
The exact shapes of the islands, riverbanks and bridges are not important.
We can replace each area of land by a vertex and each bridge by an edge. The Königsberg problem then becomes a graph problem.
We use the same labels throughout: A = North bank, B = Central island, C = Eastern area, D = South bank.
💡
Question: What is the degree of each of the four vertices?
Is there anything unusual about the four numbers?
Reveal answer
The degrees are:
- A (North bank): 3
- B (Central island): 5
- C (Eastern area): 3
- D (South bank): 3
So every one of the four vertices has odd degree.
That turns out to be the crucial clue.
Why do odd vertices cause trouble?
Imagine that you arrive at an area of land by crossing a bridge.
If your walk is going to continue, you must leave again across a different bridge.
So, for every land area that you visit in the middle of your walk, the bridges naturally come in pairs:
one bridge in + one bridge out
Every time you arrive, you need another unused edge to leave. So the edges at a middle vertex come in pairs.
That means a vertex which is neither the start nor the finish needs an even number of edges.
💡
Think about it: What can be different about the place where you start and the place where you finish?
Reveal answer
At the starting vertex, you can leave without first arriving.
At the finishing vertex, you can arrive without leaving again.
So the start and finish are the only two vertices that are allowed to have an odd degree.
Every other vertex must have even degree, because its edges have to be paired:
enter + leave enter + leave …
For a connected graph:
- No odd-degree vertices → you can use every edge exactly once and finish where you started.
- Two odd-degree vertices → you can use every edge exactly once, starting at one odd vertex and finishing at the other.
- More than two odd-degree vertices → it is impossible.
Now apply the rule to Königsberg
Earlier, we replaced the Königsberg map with the graph below. Now we can return to it and use what we have discovered about odd-degree vertices to settle the original bridge problem.
This graph has 4 vertices and 7 edges. The degrees are 3, 5, 3, 3 — so all four vertices have odd degree.
But a successful walk can have at most two odd-degree vertices.
So, was it ever possible to cross all seven bridges exactly once?
Reveal answer
No. It is impossible.
All four vertices in the Königsberg graph have odd degree. A route which uses every edge exactly once can have at most two odd-degree vertices.
It does not matter where you start, which bridge you try first, or how cleverly you choose your route — eventually you must get stuck.
So the problem was not that nobody had yet found the right route. There was no such route to find.
Euler’s idea
In 1736, the mathematician Leonhard Euler (read: oil-er) studied this problem. Instead of worrying about the shapes of the islands or the lengths of the bridges, he kept only the information about which pieces of land were connected.
This is one of the ideas that helped give rise to graph theory.
A route which uses every edge of a graph exactly once is now called an Euler trail.
Practice Puzzles
For each puzzle, assume the graph is connected. Decide whether it is possible to travel along every edge exactly once.
Puzzle 1 — Four even vertices
A graph has vertex degrees:
2, 2, 2, 2
Can you travel along every edge exactly once?
Reveal answer
Yes.
There are no odd-degree vertices, so such a route is possible.
In this case you can finish at the same vertex where you started.
Puzzle 2 — Where must you start?
A graph has vertex degrees:
3, 2, 2, 1
Is a route possible? If so, where must it start and finish?
Reveal answer
Yes.
There are exactly two odd-degree vertices: the vertices of degree 3 and degree 1.
The route must start at one of these odd vertices and finish at the other.
Puzzle 3 — Too many odd vertices
A graph has vertex degrees:
3, 3, 3, 1
Can you travel along every edge exactly once?
Reveal answer
No.
All four vertices have odd degree.
A route using every edge exactly once can have at most two odd-degree vertices.
So this graph has the same kind of problem as the Bridges of Königsberg.
Puzzle 4 — Find the actual route
a) What is the degree of each vertex?
b) Is a route using every edge exactly once possible?
c) If it is possible, can you find one?
Reveal answer
The degrees are:
A = 2, B = 2, C = 3, D = 2, E = 1.
There are exactly two odd-degree vertices: C and E.
So a route is possible, and it must start at one of C and E and finish at the other.
One possible route is:
C → A → B → C → D → E
This uses every edge exactly once.
Challenge
A connected graph has exactly six vertices of odd degree.
Could adding or removing just one edge ever make it possible to travel along every edge exactly once?
Reveal answer
No.
Adding or removing one edge changes the degree of exactly two vertices — its two endpoints.
So one change can reduce the number of odd-degree vertices from six to at best four.
But we need either zero or two odd-degree vertices.
Therefore one edge change cannot be enough.
Come back to it later
When you learn something new, it is important to come back to it later. Revisiting an idea after some time has passed helps you discover what you remember, what needs another look, and often makes the idea clearer the second time around. Our handouts are a perfect excuse to do exactly that.
Printable Graphs course
Prefer paper, a tablet, or studying offline? Open the printable version of the whole Graphs course, including this lesson.
Open printable PDF →Bridges of Königsberg handout
Get the printable handout for this lesson on its own.
Get the lesson handout →What did you think?
Whether you explored this together or worked independently, we would love to hear from both learners and parents. Tell us what you enjoyed, what was confusing, or what you would like to see next.
Share your feedback
The form is short and you do not need to give your name.