The seven bridges of Konigsberg puzzle

7 Bridges, 0 Solutions, and 1 Idea that Changed Mathematics Forever

The sun dipped low over the bustling City of Königsberg, casting golden reflections over the Pregel River. Its waters divided the town into four distinct land masses, connected by seven foot-bridges that had become a curious point of both pride and frustration for its residents.

By day, the bridges bustled with merchants and townsfolk, but as the evenings drew in, they became the source of a mysterious puzzle.

Could someone, starting from any point on land, cross each of the seven bridges exactly once and return to where they began?

It may sound simple, almost trivial, yet no matter how the townspeople tried, no one could find a solution.

As we can see above, the city comprises 4 distinct land masses, connected by 7 bridges. We aim to cross each bridge exactly once and return to our starting point. For the pedants out there, let’s clarify the rules a little bit:

You can start on any of the sections of land you like, but you may not begin on a bridge,
You may not partly cross a bridge and turn around halfway
You may not use a bridge more than once
Swimming, sailing, or any other method of aquatic transportation is not allowed

In the 1700s, mathematician Leonard Euler famously proposed a proof as to why there is no solution to this puzzle. Before we get to it, let’s introduce some simple concepts from Graph Theory that we’ll use to help us.

Let’s start with the basics. A graph is a network of nodes (points) connected with edges (lines).

We often name the nodes to make them easier to refer to (A, B, C, … ). We can talk about an edge in the graph by giving the name of the 2 nodes that it connects (for example, we could refer to the edge from A to B).

We can use a graph to model many different situations and scenarios. For this puzzle, we can use nodes to represent our land masses and edges to represent the bridges connecting them.

This is what the city of Königsberg and its bridges would look like if we represent it as a graph:

The city of Königsberg and its bridges encoded in a graph

It’s this abstraction from reality that provides us the tools to form an argument as to why there are no solutions to the puzzle.

There’s one last definition we need before we can get started. The degree of a node is the number of edges connected to it. So, in the graph below, nodes A and C have degree, 3, and nodes B and D have degree, 2.

Graph with different degree nodes: δ(A) = δ(C ) = 3, δ(B) = δ(D) = 2

So how did Euler use these ideas to prove there are no solutions to the puzzle? Let’s start with a simple example and work our way up.

In the graph below, all nodes each have degree 2. There’s also clearly a route that uses every edge exactly once before returning to the start: A → B → C → D → A.

Graph that does have a solution to the problem

So what makes this graph different?

Whenever we arrive at a node, there’s always another edge we can use to leave it. The edges come in pairs. This means that we always have a way back to where we started.

In other words, every node has an even number of edges connecting to it — they all have even degree.

This condition is necessary for a solution to exist. If it isn’t true, there can’t be any solutions.

Let’s take another look at the Königsberg graph.

Counting the degree of each node, we see that A=3, B=3, C=3, and D=5. All vertices have odd degrees, so there can’t be any solutions.

Let’s introduce one more piece of mathematical terminology. A route through a graph that uses each edge exactly once before returning to the start node is known as an Eulerian Circuit. This is the type of route we’ve been searching for in this puzzle.

So far we’ve established that:

If any node has odd degree then it is not possible to find an Eulerian Circuit.

But what happens if we consider the inverse of that statement:

If all nodes have even degree, does that mean that a solution definitely exists?

This is a slightly trickier problem to solve, but turns out the answer is yes —

if we only have even degree nodes, then there must be an Eulerian circuit.

We won’t go into the details of that proof here though.

There’s one last problem left to consider: What’s happened to the city of Königsberg since the 1700s?

Well besides a change of name (now Kaliningrad), the city looks a little different today. If we look closely, we can see that the bridges have changed too. Zooming out a little, there are now 9 bridges, and their layout is different to before.

Let’s see if today’s city has a solution to the original problem!

Graph encoding of new Königsberg Problem

There are 2 vertices with odd degrees and 2 vertices with even degrees, so sadly there’s still no solution.

However…

What we’ve stumbled across here is a special case — while it’s not possible to find an Eulerian Circuit, there is another “almost solution” we can find.

An Eulerian Path is a route through a graph that uses every edge exactly once but does not necessarily return to the start.

It turns out that when you have a graph with exactly 2 odd-degree nodes, there is an Eulerian Path that begins at one odd-degree node and ends at the other.

In this case, there is a route using every edge starting at C and ending at D:

Eulerian Path route starting at C and ending at D

Finding one of these routes might seem much easier, but take another look at the original Königsberg puzzle again — it’s not possible to do! There will always be one bridge that you won’t be able to reach.

It’s also not possible to find a route like this if we don’t start at an odd-degree node. Try it for yourself!

The Bridges of Königsberg may have seemed like a whimsical puzzle to the residents of its time, but it has had far wider implications for the study of mathematics since then.

Euler’s solution to this problem is widely regarded as the birth of the field of graph theory, a very different mathematical discipline from the algebra and equations that came before it. Since then, it has lead to the development of many different ideas both within and beyond the world of mathematics. The internet, map and navigation systems, and delivery networks all depend on ideas from Graph theory.

While the bridges may have changed, their legacy remains. It serves as a timeless reminder of how simple questions can lead to profound discoveries that reshape the way we understand the world.

All images used are by the author unless stated otherwise.