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.
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.
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 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.
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.
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.
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.
So far, we know that in any Eulerian path, all the intermediate vertices must have an even degree.
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.
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.
For Eulerian paths, that are not cycles, there should be exactly two vertices with an odd degree. All other vertices should have an even degree.
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.
For Eulerian cycles, all vertices are of an even degree.
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.
A graph has seven vertices with an even degree and no vertices with an odd degree
This graph contains an Eulerian path (but not an Eulerian cycle)
A graph has three vertices with an even degree and four vertices with an odd degree
In this graph, it is possible to find an Eulerian cycle
A graph has five vertices with an even degree and two vertices with an odd degree
It is not possible to find an Eulerian path or an Eulerian cycle in this graph
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.
Learn Graph Algorithms in C++
Graph algorithms are the core of many real-world applications of computer science, such as automotive navigation or routing in computer networks. They’re also a common subject in coding interviews at top-tier tech companies. In this course, we’ll learn about the basic concepts of graph theory and how to represent graphs as data structures in code. We’ll study essential graph algorithms such as depth-first search or Dijkstra's algorithm to traverse graphs and find shortest paths. Finally, we’ll learn to solve more complex optimization problems on graphs, such as matching and network flow problems.
A Visual Introduction to Algorithms
Learn introductory computer science algorithms, including searching, sorting, recursion, and graph theory through a combination of articles, visualizations, quizzes, and coding challenges. Implement Challenges in Java, Python, C++ or Javascript.
Mastering Algorithms for Problem Solving in Python
As a developer, mastering the concepts of algorithms and being proficient in implementing them is essential to improving problem-solving skills. This course aims to equip you with an in-depth understanding of algorithms and how they can be utilized for problem-solving in Python. Starting with the basics, you'll gain a foundational understanding of what algorithms are, with topics ranging from simple multiplication algorithms to analyzing algorithms. Then, you’ll delve into more advanced topics like recursion, backtracking, dynamic programming, and greedy algorithms. You'll also learn about basic graph algorithms, depth-first search, shortest paths, minimum spanning trees, and all-pairs shortest paths. By the end of this course, you'll have acquired a wide range of skills that will significantly enhance your ability to solve problems efficiently in Python. Through this course, not only will you improve your coding skills, but you will also gain confidence in tackling complex problems.