Seven bridges, one question, and the start of graph theory

Before graph theory existed, there was just a city and a question.

The city was Königsberg. The river was the Pregel. The river split the city into four pieces: two banks and two islands in the middle. Seven bridges held it all together.

The people of Königsberg liked to walk on Sundays. They had a question they couldn’t answer.

Can you walk through the city, cross every bridge exactly once, and end up back where you started?

They tried. Every walk left a bridge uncrossed, or crossed one twice. Nobody could do it. Nobody could prove it was impossible either.

The question reached a Swiss mathematician named Leonhard Euler. He looked at the map and saw something different.

The trick: forget the city

Euler didn’t care about the size of the islands. He didn’t care about how long each bridge was. He didn’t care which streets you took to get from one bridge to the next.

What mattered was which pieces of land were connected to which other pieces, and by how many bridges.

So he drew a picture with four dots and seven lines.

• Each dot was a landmass: A, B, C, D.
• Each line was a bridge.
• Two lines between A and B meant two bridges.

That picture is called a graph. The dots are vertices. The lines are edges.

Königsberg looked like this in graph form:

• Between A and B: 2 bridges
• Between A and C: 2 bridges
• Between A and D: 1 bridge
• Between B and D: 1 bridge
• Between C and D: 1 bridge

Seven edges total. Four vertices. The whole city, reduced to its bones.

Why the walk is impossible

Now the question is easier to ask. Can you trace every line in this picture, exactly once, and end where you started?

The answer is no. Here is why.

Pick any landmass. Count how many bridges touch it. That number is called the degree of the vertex. For Königsberg:

• deg(A) = 5
• deg(B) = 3
• deg(C) = 3
• deg(D) = 3

All four are odd numbers. That turns out to matter a lot.

Imagine you are on your walk. You arrive at a landmass by crossing a bridge. To leave, you cross a different bridge. Every time you visit, you use up two bridges — one to enter, one to leave.

In, out. In, out. In, out. The bridges at each landmass have to pair up.

If a landmass has an even number of bridges, the pairing works out. Every entry has its exit. You can come and go cleanly.

If a landmass has an odd number of bridges, the pairing fails. One bridge is left unpaired. You either get stuck there or you skip a bridge.

Königsberg has four landmasses with an odd number of bridges. There is no way to pair them all up. The walk is impossible.

That’s the proof. No tools, no equations beyond counting. Just an idea: every visit costs two bridges.

What about a walk that doesn’t return home?

Euler also worked out a softer version of the puzzle. What if you don’t have to end where you started?

Then you’re allowed up to two odd-degree landmasses — the start and the end. You enter the start without arriving, and you leave the end without departing. Those are the two unpaired bridges, and they’re fine.

But Königsberg has four odd-degree landmasses. Two more than the rule allows. Even the easier version is impossible.

A twist from history

The story doesn’t end in the 1700s.

In World War II, Königsberg was bombed. Two of the seven bridges were destroyed. The city was rebuilt and renamed Kaliningrad.

When two bridges were lost, the degrees changed. Some odd numbers became even. The parity of the graph shifted.

After the bombing, the walk that had been impossible for two hundred years was suddenly possible.

The math didn’t change. The graph did.

Why this still matters

Euler did one thing in this proof, and it was bigger than the puzzle.

He took a real, physical thing — a city, a river, seven bridges — and threw away everything that didn’t matter. Distances, sizes, shapes. He kept only what was connected to what. The connections were the whole problem.

Almost three hundred years later, that move is everywhere. The internet is a graph. Your social network is a graph. The call structure of your code is a graph. The roads between cities are a graph. Each one is solved the same way Euler solved Königsberg: forget the picture, count the connections.

A graph is what’s left when you take a real thing and throw away everything except how it’s wired.

Next post

In the next post, I’ll show how to put the seven bridges into a Neo4j database with Cypher queries. We’ll search for Eulerian circuits in code. Then we’ll knock out the two bridges that were destroyed in the war and see how the answer changes.

The walk that was impossible for two centuries is one Cypher query away.