The Seven Bridges of Königsberg and other related problems

Where it all started!

Let’s consider the landscape shown in the image below. This is from the eighteenth century (1700s), where the Pregel river flows through the city of Königsberg, dividing it into parts. These parts of land were connected through seven bridges. This led to the famous Seven Bridges of Königsberg Problem, which is described below.

The Seven Bridges of Königsberg Problem

People often wondered how to travel through these bridges in such a way that:

• They are allowed to start and end their journey at any part.

• They are allowed to travel from one part to another using the bridges only.

• During their travel, each bridge must be crossed exactly once.

Many people tried and failed; they wondered what went wrong, and what route they should take to solve this puzzle.

Is the problem solvable?

In 1736, the famous mathematician Leonhard Euler solved this mystery by showing that a solution to the Seven Bridges of Königsberg Problem was not possible. He transformed the problem into a structure that is now known to us as graphs. Before moving forward, let’s define what graphs are.

Graphs

Graphs are mathematical structures that consist of sets of vertices and edges. Each vertex is a point in a graph that is usually drawn as a circle with its name written inside. Every edge represents a connection or a link between two vertices. It is drawn as a line connecting the corresponding vertices.

Transforming the puzzle into a graph

Going back to the Seven Bridges of Königsberg Problem, we can convert the given map into a graph. Here, every part of the land can be represented by a vertex. Notice that every bridge connects exactly two pieces of land. Hence, each bridge can be represented as an edge. The following slides give a visual description of how such graphs are created.

This type of transformation and visual representation is useful in representing road networks, air-traffic connections, communication networks, and many others.

Some terms used in graph theory

Graphs come in different flavors. A directed graph is unidirectional, which simply means that we can travel through the edges in only one direction. A one-way road is one such example. In such graphs, the edges are drawn with an arrow pointing toward the direction in which we are allowed to travel.

In the Seven Bridges of Königsberg and other related problems, we can travel through these bridges in both directions. This means that the direction is not important when we draw the underlying graph. Such graphs belong to the category of undirected graphs.

If a graph contains parts that are disconnected, then such graphs do not fall under the category of connected graphs. In this blog, we will only discuss those undirected graphs that are connected as well.

Multi-graphs can have more than one edge between any pair of vertices. Moreover, the number of edges associated with a vertex is the degree of that vertex.

If a solution to the Seven Bridges of Königsberg or a similar problem exists, then such a path is called an Eulerian path (or Eulerian tour). In case the path ends at a vertex from where we started our journey, then we have actually gone through a cycle or a loop. In this case, such a journey will be called the Eulerian cycle (or Eulerian circuit).

In any path—particularly the Eulerian path—there is a start vertex, an end vertex, and the rest of the vertices. Let’s call the rest of the vertices as intermediate vertices, which will have an even number of edges. This is because these edges come in pairs, one for entering the vertex and another one for leaving.

When can we solve it?

Let’s revisit the problem. This time, instead of looking at the seven bridges and the land, we will look at the corresponding graph. We will analyze this graph using the tools that we’ve just learned. If the underlying graph contains an Eulerian path, then we have only one information regarding the solution.

Let’s divide the problem into the following two scenarios:

• The start and end vertices are different.

• The start and end vertices are the same.

The start and end vertices are different

Let’s look at the edges of the start vertex. We start the journey from the start vertex and leave the vertex using one edge. Now, if we were to revisit the start vertex, using an edge, we’d have to leave using another one. This means that all preceding edges will come in pairs. Therefore, the start vertex will have an odd number of edges.

A similar argument can be used to show that the end vertex will also have an odd number of edges.

The start and end vertices are the same

Since the start and end vertices are the same, we are talking about Eulerian cycles. We begin from the start vertex and leave it using one of the edges. Since the start vertex is also the end vertex, we need to come back to this vertex again and complete the cycle. If there are more edges, then we will leave this vertex from a different edge, and later come back using another edge. Once again, we can group the edges of this vertex in pairs. This means that the degree of this vertex is also even. In this case, it implies that all the vertices have an even degree.

When can we not solve it?

This above discussion implies that if the graph has more than two vertices with an odd degree, then an Eulerian path (or cycle) cannot exist. Let's revisit the graph corresponding to the Seven Bridges of Königsberg Problem and count the number of vertices with odd degrees.

Let’s test what you understood

Fun fact

Over time, some of the Königsberg bridges were destroyed and some new ones were built. The map of the area has changed. The following illustration shows the current map, with the bridges that are currently present.

Can you figure out whether this new puzzle can be solved or not?

This topic is related to graphs and algorithms. If you want to learn more about algorithms, have a look at the following interesting courses.