WEEKLY PROBLEM

The Seven Bridges of Königsberg

Can you cross every bridge exactly once?

Difficulty: ★★★☆☆ Topic: Mathematics · Logic · Computer Science

The Problem

Imagine the city of Königsberg in Prussia in the eighteenth century. The city was divided by a river, with two islands sitting in the middle. Seven bridges connected the islands and the riverbanks.

The townspeople had a deceptively simple question:

Can you take a walk through Königsberg that crosses each of the seven bridges exactly once?

You may start wherever you want. You may finish wherever you want. You may cross land as many times as you like. But every bridge must be crossed once and only once.

It sounds like something you should be able to solve simply by drawing a route and trying different possibilities.

But there is a catch.

No matter how clever your route is, you will eventually get stuck.

Your Challenge

Before reading further, try to solve it yourself. Grab a piece of paper and draw four regions representing the two riverbanks and the two islands. Connect them with seven lines representing the bridges.

Then try to find a route that:

crosses every bridge,
crosses each bridge exactly once, and
never teleports between locations.

Can you do it?

🔎 Reveal the answer

“`

The answer: No.

Euler proved that such a walk is impossible. But the interesting part is why.

Euler realized that the actual shape of the city did not matter. Neither did the length of the bridges, the distance between the islands, or the precise geometry of the river.

What mattered was simply how the different regions were connected.

So Euler transformed the problem into something much more abstract. He represented each landmass as a vertex (or node), and each bridge as an edge.

The resulting structure looks something like this:

    Landmass
      ●
     /|\
    / | \
   ●--●--●

Now we can forget about Königsberg entirely. We only need to ask a mathematical question about the resulting graph.

The crucial observation

Count how many bridges touch each landmass. This number is called the degree of a vertex.

In the Königsberg graph, all four vertices have an odd degree.

And this creates a problem.

Whenever you enter a landmass through a bridge, you normally need another unused bridge to leave it. Bridges therefore naturally come in pairs: one to enter and one to leave.

The only exceptions can be the beginning and the end of your journey. Therefore, a graph can have:

zero odd vertices if the walk starts and ends at the same place, or
exactly two odd vertices if the walk starts and ends at different places.

But Königsberg has four odd vertices.

Therefore, there is no possible route that crosses every bridge exactly once.

The rule:
A connected graph has a route using every edge exactly once if and only if it has 0 or 2 vertices of odd degree.

Why This Problem Changed Mathematics

Euler’s solution was much bigger than the puzzle itself. He showed that you could solve a problem about a physical city by throwing away almost everything about the city.

The bridges became edges. The landmasses became vertices. The walk became a sequence through the graph.

This was one of the foundations of what we now call graph theory.

And graph theory is everywhere in modern technology. Computer networks, GPS navigation, social networks, web search, recommendation systems, logistics, circuit design and many AI systems can all be described using graphs.

In other words, Euler was not merely solving a puzzle about seven bridges. He was discovering a powerful way of thinking:

Sometimes the key to solving a problem is figuring out what information you can safely ignore.

Think About It

Here’s your follow-up challenge:

What is the smallest change you could make to the Königsberg bridge system that would make the walk possible?

Would you need to remove a bridge? Add one? Move one? Can you find a solution with only one change?

“`

🧠 What did we learn?

Concept: Graph Theory
Key idea: Eulerian paths
Computer Science connection: Networks, routing and algorithms
Historical figure: Leonhard Euler

Weekly Problem #1
Did you solve it before revealing the answer?

Weekly Problem: Seven Bridges