Euler Paths
Euler paths are a fundamental concept in graph theory, a field that explores the relationships between points (vertices) and lines (edges) in a mathematical structure. Originating from a historical problem involving the Seven Bridges of Königsberg, Euler paths allow for traversing a graph such that each edge is crossed exactly once. The criteria for the existence of an Euler path are tied to the degrees of the vertices: if every vertex has an even degree, an Euler circuit can be formed, starting and ending at the same vertex; if exactly two vertices have an odd degree, an Euler path can exist, starting at one of these odd vertices and ending at the other.
Graph theory, including Euler paths, finds applications in various modern issues, such as optimizing delivery routes, analyzing social networks, and mapping biological patterns. In scenarios involving directional edges, like one-way streets, directed graphs (digraphs) come into play, where the direction of travel is restricted. Additionally, edges can be assigned weights to represent costs, facilitating the search for minimal weight paths. While graph theory provides visual tools to tackle complex problems, it also highlights the limitations, as not all real-world issues can be neatly solved using these mathematical models. Nonetheless, the connection between practical challenges and graph-theoretical frameworks allows for the use of established algorithms to achieve effective solutions.
On this Page
Subject Terms
Euler Paths
Graph theory is a relatively new but rapidly growing area of discrete mathematics. A graph consists of a set of vertices (points in space), and the edges that connect them. Figure 1 shows a graph with six vertices and seven edges, one of which is a loop. Although vertices in a graph do not need to be connected to an edge, every edge must begin and end at a vertex.
The origin of graph theory can be traced back almost three centuries with a problem posed around the concept of what is now known as an Euler path. An Euler path through a graph travels along each edge exactly once. Because of their simplicity, Euler paths provide a good introduction to graph theory and its applications.
Overview
In 1736, Leonhard Euler published an essay that attempted to solve the Seven Bridges of Königsberg problem. The problem is as follows: There are seven bridges in Königsberg that connect 4 different landmasses, as shown in figure 2. Starting on land, is there a way to take a walk that crosses every bridge exactly once?
By creating an abstract graph of the Königsberg map, Euler was able to prove that such a walk was impossible. He represented each landmass with a vertex and each bridge with an edge connecting the respective vertices (landmasses), as shown in Figure 2. Euler then summed up the number of times an edge entered or exited a vertex and labeled this sum as the degree of the vertex (see Figure 3). Using mathematical logic, he concluded that an Euler path through a graph exists if and only if either every vertex has an even degree or exactly two vertices have an odd degree. When every vertex has an even degree, it is possible to find an Euler path that begins and ends at the same vertex. This is known as an Euler circuit.
Euler paths and Euler circuits show up in a wide range of contemporary problems ranging from mapping DNA patterns or social networks to planning snowplow routes through city streets. In some cases, such as a one-way street, a snowplow is permitted to travel along an edge only in a single direction. This results in a directed graph, or digraph. It is also useful in many cases to associate each edge with a weight, or cost. For example, in planning delivery routes within a region, the weight of each edge might be the distance between the cities. Graph theory methods could then be used to find an Euler path of minimal weight.
Although graphs can help visualize complex systems, this does not always mean that an optimal solution can be found. In fact, it is just as likely that using a graph to describe a scenario allows one to realize that the problem is still an unsolved problem in mathematics. However, by connecting the real life problem with its corresponding problem in graph theory, it is possible to take advantage of several known algorithms that produce reasonably good outcomes.
Bibliography
Agnarsson, Geir, and Raymond Greenlaw. Graph Theory: Modeling, Applications, and Algorithms. Upper Saddle River, NJ: Pearson, 2007.
Aufmann, Richard, Joanne Lockwood, Richard Nation, and Daniel K. Clegg. Mathematical Excursions. 3rd ed. Belmont, CA: Brooks, 2013.
Epp, Susana S. Discrete Mathematics and Applications. Boston: Cengage, 2011.
Marcus, Daniel A. Graph Theory: A Problem Oriented Approach. Washington, DC: Mathematical Assoc. of America, 2008.