Solution: Math Puzzle: The Seven Bridges of Königsberg
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.
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?