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 start somewhere in the city and cross all seven bridges exactly once, without using any bridge twice? Try tracing a route with your finger, using the interactive below, or sketching one on paper.
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.
💡
A graph is connected if you can get from any vertex to any other vertex by following edges. If this is not possible, the graph is disconnected.
Question: What is the degree of each of the four vertices?
What do all four degrees have in common? Hint: it’s something we already considered in Lesson 1.
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 …
Think about it: We saw that the start and finish of an Eulerian path can have odd degree. But how could the start and finish instead have even degree? Hint: What changes if you finish at the same vertex where you started?
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 Eulerian path.
Practice Puzzles
For each puzzle, assume the graph is connected. Decide whether it is possible to travel along every edge exactly once. Where possible, sketch an example graph with the given degrees before opening the answer.
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? Optional drawing challenge: try to sketch a graph with these degrees. You will find that it cannot be made as a simple graph; here we are allowed to use a multigraph, as in the Königsberg example.
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.
Here every vertex has degree 5, so all six are odd. Remove the highlighted edge and its two endpoints drop to degree 4. The other four vertices stay odd.
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.
Download the printable lesson materials, practice and answers for Bridges of Königsberg.
Find the resources →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.