The Seven Bridges of Konigsberg

Konigsberg is a town in former Prussia that is built around the Pregel River.  In the eighteenth century, there were seven bridges that connected different parts of the town that the townspeople enjoyed using for their evening strolls.  However, it seemed that no matter where they started or which way they went, the townspeople could not find a route that used all seven bridges exactly once.  Finding such a route became known as the as the Seven Bridges of Konigsberg Problem.

The Seven Bridges of Konigsberg Problem:

Find a walkable path that crosses each bridge exactly once.

In 1736, the Swiss mathematician Leonhard Euler proved that there was no route in Konigsberg that used all seven bridges exactly once.  He reinterpreted the problem by changing all the islands to points and all the bridges to line segments.  Euler then reasoned two things for a continuous (or walkable) path to exist in such a system:

1) Every point except for the starting and ending points must have an even number of line segments connected to it (because it would need n times to enter and n times to exit for a total of 2n). 

2) There can be at most two points that have an odd number of line segments connected to it – the starting and ending points.

In the Konigsberg problem, all four points have an odd number of line segments connected to it (the northern island is connected by 3 bridges, the western island is connected by 5 bridges, the eastern island is connected by 3 bridges, and the southern island is connected by 3 bridges), so a solution is impossible.

The Seven Bridges of Konigsberg Problem:

Reinterpreted as points and line segments.

The same reasoning can be used on problems where you must draw a figure without lifting your pencil, such as this picture of a house below:

The House Problem:

Draw this house without lifting your pencil.

Reinterpreting this house as points and line segments, like Euler did with the seven bridges of Konigsberg, shows the following:

The House Problem:

Reinterpreted as points and line segments.

The top point on the roof has 2 line segments connected to it, the bottom points of the roof have 4 line segments connected to it, the middle point inside the house has 4 line segments connected to it, and the bottom points of the house have 3 line segments connected to it.  Since all points have an even number of line segments connected to it except for the bottom two, we know that it is possible to draw this figure with a continuous line.  We also know that these bottom two points must be the starting and ending points since they are the only two points with an odd number of line segments connected to them.  Now that we know the trick of finding the starting and ending points, discovering a way to draw this picture with one continuous line becomes much easier.  One solution is as follows:

The House Problem:

One solution.

but there are many other solutions as well.

My son and I recently built an arcade machine where these theorems came in handy.  We wanted to place some lights around some of the edges of the arcade, and to keep it simple, we wanted to use just one continuous string of lights. 

We originally wanted to place a border around the top marquee sign, a border around the playing area, and another border around the keyboard drawer.  However, no matter how many times we tried, we couldn’t do it.  Reinterpreting this as a system of points and line segments showed us why:

Since there were more than two points with an odd number of line segments connected to it, it was impossible to place a continuous string of lights in this way.  So we revised the design so that there was a border around just the sign and the playing area, and not around the keyboard drawer, like this:

Now all but two points have an even number of line segments, making it possible for us to place a continuous string of lights in the way described.  We also knew that the middle two points (under the sign but above the playing area) with the odd number of line segments connected to them had to be the starting and ending points.  Therefore, one way to place a continuous string of lights as pictured would be as follows:

which is exactly how we did it.

The Seven Bridges of Konigsberg Problem started out as a simple challenge between some townspeople who enjoyed going on evening strolls.  Euler reinterpreted the problem as a diagram of points and lines, and discovered some basic theorems that are foundational to a branch of mathematics called graph theory.  These theorems have several applications, including how to solve puzzles in which you must draw a certain picture without lifting your pencil, drawing workable electrical diagrams, and much, much more.  It is truly amazing how versatile these simple theorems are.