Solution: The Seven Bridges of Königsberg Math Puzzle

The Swiss mathematician Leonhard Euler became interested in the Königsberg bridge problem. In 1736 he published a paper showing that it was not possible to find a path that would cross each bridge just once without missing any of them. Here’s why:

Let’s label each of the landmasses with a red uppercase letter and each of the bridges with a blue lowercase letter.

We can regard each of the landmasses as a point and each of the bridges as a line. In this way the map is equivalent to the diagram below:

We call a diagram like this a network. Each of the points A, B, C, and D is called a vertex. (The plural of vertex is vertices.) Each of the lines, a, b, c, d, e, f, and g is called an arc. We refer to the number of arcs that meet at a vertex as the degree of that vertex. The degree of vertex A is 5. The degree of each of the other three vertices, B, C, and D, is 3.

Solving the Königsberg bridge problem is equivalent to being able to draw the network pictured without lifting your pencil off the paper and without retracing any arc. We call this traveling the network.

Euler showed that a network could not be traveled if it has more than two vertices with degrees that are odd numbers. The network representing the Königsberg bridge problem has four odd vertices.

To help understand how this works, look at these two networks:

The one on the left has four vertices, each with a degree of 2. The pentagonal network has five vertices of degree 2. In both cases all the vertices are of even degree. Each of these networks can be traveled starting at any vertex and ending at that same vertex.

Now look at this network pictured to the left:

Vertices A and B are each of degree 3, which is odd. The other four vertices are of degree 2, which is even. This network can be traveled via several different paths, but the starting point must be A or B and the ending point must be the other odd vertex. Try it.

Here’s another network with two odd vertices.

It can also be traveled as long as the end points of the trip are C and D, the odd vertices.

Here’s a network that cannot be traveled because it has four odd vertices.

E and H are of 1 degree each. F and G are of 3 degrees each.

Here’s another network that cannot be traveled.

Why does this rule hold true? One way to think about it is to realize that a vertex of even degree can be entered and left during the journey. A vertex of degree 2 can be entered and left once. If it is of degree 4, there will be two trips through it. But if a vertex is of odd degree, the last trip in must be the end, since there’s no arc left to depart on. For example, if a vertex is of degree 7, there will be three complete trips through it, accounting for six of the arcs. But the last trip in on the seventh arc leaves no exit.

One could also start on a vertex of odd degree. Then all subsequent trips through the vertex would use a pair of arcs. In general, when a network has two odd vertices, they must be the beginning and end points if the network is to be successfully traveled.

Now Try This

Königsberg is now known as Kaliningrad. There are still seven bridges. Some of the original bridges remain, but others are gone and new bridges have been built. Here’s the current arrangement:

Can this new network be traveled?