The Königsberg Bridge Problem - An illustration showing seven brdiges connecting four landmasses. Island 1 (centre) is connected to the upper bank (north) and the lower bank (south) via two bridges each. Island 1 and Island 2 (east) are connected by a bridge. Island 2 is connected to the upper bank and the lower bank via one bridge each.

The Königsberg bridge problem has its origins in the Russian city of Kaliningrad. Back when the problem originated, it was known as the city of Königsberg (Prussia). This city was cut into several pieces by the waters of river Pregel (Pregolya) flowing through it.

As you can see from the title image, the river Pregel cuts the city of Königsberg into an upper bank, lower bank, Island 1, and Island 2. Island 1 is connected to the upper bank and the lower bank via two bridges each. Island 1 and Island 2 are connected by a bridge. Island 2 is connected to the upper bank and the lower bank via one bridge each. In total, there are seven bridges.

As the residents of Königsberg traversed the tricky bridges in the early 18-th Century, a curious question popped up among them:

Given any starting point, would it be possible for a resident to travel through the city such that each bridge in Königsberg is used only once? If so, how?

Thus, the Königsberg bridge problem was born. It is now your turn to try and solve this little logic problem.

Spoiler Alert:

If you wish to solve this puzzle on your own, I suggest that you pause reading this essay at this point. Once you are done, you may continue reading from here. Beyond this point, I will be explicitly discussing solutions to this problem.

This essay is supported by Generatebg

A product with a beautiful background featuring the sponsor: Generatebg - a service that generates high-resolution backgrounds in just one click. The description says "No more costly photographers" and displays a "Get Started" button beneath the description.

The Königsberg Bridge Problem Setup

The first thing that I wish to do with this problem is to number the bridges for ease of reference later. Consequently, the city map now looks as follows:

The Königsberg Bridge Problem — From left to right: Bridges 1 and 3 connect the upper bank with island 1. Bridges 2 and 4 connect the lower bank with island 1. Bridge 5 connects island 1 with island 2. Bridge 6 connects island 2 with the upper bank. Finally, Bridge 7 connects the lower bank with island 2.
Numbered Bridges — Illustration created by the author

Now that we have numbered bridges, we could refer to various routes using number sequences like: 1–2–4–3. The corresponding route would appear as shown below:

The Königsberg Bridge Problem — A black curvy line starts from the upper bank, takes bridge 1 to reach island 1. From there it takes bridge 2 to the lower bank. Then takes bridge 4 to go back to island 1. Finally, it takes bridge 3 to reach the upper bank again.
Path 1–2–4–3 (Illustration created by the author)

Now, let us see how far we can proceed along this path.

The Trial-and-Error Approach to the Königsberg Bridge Problem

From 1–2–4–3, we could head to bridge 6 which connects the upper bank with Island 2. From thereon, we have two options, either take bridge 5 to go back to Island 1 or take bridge 7 to go back to the lower bank. Here’s how the path would look if we took 1–2–4–3–6–7:

The Königsberg Bridge Problem — Picking up from the last image (path 1–2–4–3), the curvy line now takes bridge 6 to reach island 2. From there, it takes brige 7 to reach the lower bank again. At this point there is nowhere else to go without reusing any of the earlier bridges. So, the path remains “stuck” in the lower bank.
Path 1–2–4–3–6–7 (Illustration created by the author)

As you can see, we have ended up stuck after traversing a total of six bridges. If we had used bridge 5 instead of bridge 7, we would have ended up stuck as well. The question now is if this is a specific issue with the route we chose or if the puzzle just does not yield to traversing all seven bridges just once.

If you had tried to solve this puzzle on your own, you would have realized that regardless of your starting point, six appears to be the maximum number of bridges that we can use only once. So, gut feeling says that it is impossible to use all seven bridges only once. So, how are we going to know for sure that there isn’t at least one super tricky solution to this problem?

Reducing the Königsberg Bridge Problem

In order to start figuring out if we are up against an impossible task, let us first reduce the problem to see what is going on. To this end, I ask the following question:

What is the minimum number of bridges that we could use only once (each) before we end up stuck?

Take a moment to ponder upon this question. Just by trial-and-error, we could establish that we can never get stuck by traversing two bridges using each only once. So ‘2’ is no problem. However, with ‘3’ combinations start popping up where we do end up stuck! Here is one such example (6–3–1):

The Königsberg Bridge Problem — The curvy line depicting the path starts from island 2 and takes bridge 6 to reach the upper bank. Then it takes bridge 3 to reach island 1. Finally, it takes bridge 1 to reach the upper bank again. At this point, there is nowhere else to go without reusing any of the earlier bridges. So, the path remains “stuck” in the upper bank.
Path 6–3–1 (Illustration created by the author)

Based on this insight, let us reconstruct the problem using just three bridges. In this case, I choose to go with bridges 3, 4, and 5 as shown below:

The Königsberg Bridge Problem — In this setup, all other bridges except 3, 4, and 5 have been removed. The path starts from the upper bank and takes bridge 3 to reach island 1. Then, it takes bridge 4 to reach the lower bank. At this point, there is nowhere else to go without reusing any of the earlier bridges. So, the path remains “stuck” in the lower bank.
Path 3–4–5 (Illustration created by the author)

There are 3! (3 factorial) combinations of paths that we could choose to traverse this setup:

a) 3–4–5

b) 3–5–4

c) 4–5–3

d) 4–3–5

e) 5–4–3

f) 5–3–4

Regardless of which option you choose, you would end up stuck. Solving this problem involving three bridges is essentially the same as solving the problem with seven bridges. Based on this, we could say for certain that the Königsberg bridge problem is impossible to solve.

Final Remarks

In 1735, famous mathematician Leonhard Euler worked out an elegant way to figure out the mechanics of this problem. He remarked that if we neglect the two bridges featuring the starting point and the ending point, all other bridges we traverse should necessarily feature two terminals (entry and exit).

Based on this, he said that each landmass in the city (upper bank, lower bank, and the two islands) must be a terminal for a total number of bridges twice the number of times the said landmass is traversed during the entire travel.

However, we note that Island 1 has 5 terminals, whereas all other landmasses have 3 terminals each. Based on this, Euler argued that it is impossible to solve the Königsberg bridge problem. His work on this problem and other related problems led to the development of mathematical fields that are known today as topology and graph theory.

Such is the rich history behind the Königsberg bridge problem. Although the seventh bridge eluded us, this problem opened the door for numerous mathematical applications we use and benefit from today!

If you’d like to get notified when interesting content gets published here, consider subscribing.

Further reading that might interest you: The Helix Puzzle — A Simple Geometric Challenge and Can You Really Solve This Third Grade Math Puzzle?

If you would like to support me as an author, consider contributing on Patreon.

Street Science

Explore humanity's most curious questions!

Sign up to receive more of our awesome content in your inbox!

Select your update frequency:

We don’t spam! Read our privacy policy for more info.