7 Bridges of Konigsberg

The satellite image (Google Earth) below shows the city of Kaliningrad, Russia. There is an island in the Pregolya river with a nice park and seven bridges indicated in the picture. Kiliningrad has changed hands many times over the centuries and in the 18th Century was  part of Prussia and called Konigsberg.

The good citizens of Konigsberg liked to take a walk on a Sunday around the island. A puzzle became very popular: “Is it possible to walk over and back to the island crossing all of the seven bridges once and only once?

The great mathematician Leonhard Euler visited the city and heard of the question. Being one of the greatest mathematicians that ever lived, he was going to try to solve it. He thought it sounded very ordinary at first:

Can you find a way around the 7 bridges? Crossing every bridge once and only once.

(Only walking allowed no swimming, flying, boating or tunnelling)

Don’t spend more than 10 minutes on this. If you can’t solve it in 10 minutes you will never solve it.

5 Bridges of Konigsberg

The Island is still there but the bridges have changes. And presumably the good citizens of Kaliningrad still go on their Sunday walks

Presumably you weren’t able to find a way around the 7 bridges. Neither was Euler!

The map above shows a satellite (Google Earth) image of Kaliningrad, Russia today with 5 bridges.

Can you try the 5 Bridges, is that possible?

8 Bridges of Konigsberg

How did you get on with 5 bridges? How will you fare with 8? In modern Kaliningrad, we can widen out our walk and include more bridges as shown below

Perhaps you were able to find a way around the 5 bridges. What about 8?

Can you try the 8 Bridges?

Don’t spend too much time on it though, we want to move on the the learning.

Problem Solving Lesson

Often times you will hear that if you try hard enough and long enough you will be able to solve a particular puzzle or problem. However, some puzzles and problems are impossible. Presumably you were not able to find a route for 7 bridges. Maybe you were able to find it for 5 bridges.  A solution is shown below. While you may be disappointed that you couldn’t solve the problem and unhappy that there is no solution, there are important lessons to learn.

The problem could be re-framed as follows:

Why can you not do the 7 bridges or the 8 bridges but you can do the 5 bridges?

Did you notice anything when you were trying different routes?

In the letter quoted above, Euler goes on to say

“This question is so banal, but seemed to be worthy of attention in that geometry, nor algebra, nor even the art of counting was sufficient to solve it.  In view of this, it occurred to me to wonder whether it belonged to the geometry of position which Leibniz had once so much longed for.  And so, after some deliberation, I obtained a simple, yet completely established, rule with whose help one can immediately decided for all examples of this kind, with any number of bridges in any arrangement ….” Leonhard Euler to Giovanni Marinoni, March 13, 1736

Can you figure what the rule might be?

Learn about Euler’s great insight below.

In 1736 Euler realised that the actual geography doesn’t matter and the problem can be represented on paper without drawing a scale map.

What matters are the land-masses which can be represented by points (nodes or vertices) and the paths between them (bridges) which can be represented by lines (edges). Euler showed that if there are 2 connections into a node then that area can be entered and left. This is also true for any even number of connections. However if there were one connection into a node then it must be a start point or end point. If there are three connections into a point then that place can be entered and left and entered again whereupon it can’t be left so it must be an end point (or indeed a starting point). The same holds true for any odd number. Of course you can only have two such points that can be end/starting points. Therefore if you have more than two vertices with odd number of connections then it is impossible to pass through every path once and only once.

See a graphical representation of this below.

This was the start of an important area of mathematics called graph theory. Graph theory is useful for describing systems where connections are important. For instance, if we wanted to describe social connections, maybe on social media we are only be interested in the people (vertices) and who they are connected to (edges). The distances and directions between people don’t matter all that matters is the connections.

Graph theory is very important now to analyse connections in the modern world with social connections, telecommunications, the internet and lots more.   It was all started by Leonhard Euler investigating a seemingly simple puzzle over 200 years before the internet.

Most of us couldn’t hope to make discoveries like Euler, but we can learn from this famous problem. What problem solving strategies did Euler use? What ones could we use?

Euler recast the problem in a new way. He came at it from a new angle.

Although Euler didn’t need to, it can often help to draw diagrams.

We could also try to simplify the problem as we did with 5 bridges.

A useful strategy is to see where and when you know you are wrong with a problem. So in this problem you might have seen that you had a problem if there were three approaches to a bridge. You might have seen that you could start and finish at these points. You might have been able to generalize that if there are an even number of connections to a point it is possible to go in and out. But, if there are and odd number of connections it is only possible if they are a start or end point.

You mightn’t found a whole new area of maths, but developing strategies like this can help you become a great problem-solver.

This is the topographical representation (the lie of the land)

The background doesn’t matter. It doesn’t matter if there is grass and water or chocolate and lemonade under the route.

The land areas can be represented by points (vertices) and the connections between them (bridges) can be represented by lines.

The length and directions of these lines don’t matter, the position of the points on the diagram don’t matter either. Mathematically it is represented by the diagram on the left. This is the fundamental of graph theory.

See other related activities

Dastardly Diagrams

Room Maze 1

Room Maze 2

Room Maze 3

If you can’t do any of these try to figure if they are possible!