Königsberg Bridge Problem & Euler Path : Can You Draw A Graph Without Removing Pen From The Paper?

What is The Königsberg Bridge Problem?
The Königsberg Bridge Problem is a famous topology puzzle which is about the solution to cross seven bridges in the city of Königsbergwithout doubling back. Konigsberg used to be a German town in the 18th century, and the city of Königsberg was set on both sides of the Pregel River. There are two islands in the river which are connected to the banks or each other with seven bridges. The residents of the town have atradition, which is, they always try to find a way to cross each bridge exactly once. Obviously this is a difficult problem if we know nothing about the topology. Leonhard Euler, a Swiss mathematician, heard about this puzzle. Finally, he provided a solution which successfully proved that the way to cross each bridge only one does not exist at all.

How Euler Resolves The Issue?
From the map, we can see there are four areas which are connected with the bridges, which are, on the north bank of the river, on the south bank of the river, and the two islands.For simplicity purposes, Euler converted the map to a graph. This graph is made up of the points, which are also called a vertex, and lines which are also called edges. So the four areas A, B, C and D are represented as vertices, and the 7 bridges are simplified as edges. So, the question now becomes: Can you draw each line only once to generate the graph, without removing your pen from the paper? Of course, you can start and end at any point, but you need to be smart enough to know which point to start with and which one to end with. If a vertex has an odd number of edges connected to it, it will be called an odd vertex. Conversely, if a vertex has an even number of edges connected to it, it will be called an even vertex. From this graph, we can see that all vertices, A, B, C and D are all odd vertices because they all have an odd number of edges connected to them. Through a few days' investigation, Euler drew the following conclusions. For a graph which can be completed with each edge being drawn only once and no removing pen from the paper, it must satisfy one of the following conditions. It must have zero odd vertices or 2 odd vertices. If a graph has zero odd vertices, we can use any vertex as the start point, and this point will be the end point as well. The path that uses every edge of a graph exactly once is also called Euler Path. Let's check this example to see if it can form an Euler Path. There are no odd vertices in this graph, we can start from any point, and it will end up coming back to this point to complete the graph. On the other hand, if the graph has two odd vertices, to successfully complete an Euler Path, one vertex can be used as the start point and another one will be the end point. Let's see this example. There are two odd points in this graph. We can use point one as the start point and the end point will be point two. For any other cases, there is no way to complete the graph without removing the pen from paper. Let's go back to the Königsberg Bridge Problem and see if we can resolve it. From the simplified graph, we can see there are four odd vertices in the graph. So, there is no way to pass each bridge only once. Before we end today's topic, you can test your knowledge by picking up the ones which can generate the Euler Path.