Eulerian Path

An Eulerian path on a graph is a traversal of the graph that passes through each edge exactly once, and the study of these paths came up in their relation to problems studied by Euler in the 18th century like the one below:

After trying and failing to draw such a path, it might seem plausible that the task is impossible. But how can this be proven? What if the configuration of bridges is slightly different? (For instance, it is not hard to cross all but one of the bridges, and adding another bridge to the existing seven would also allow a complete crossing.) Is there a way to characterize the configurations that allow for these paths? What if the path is required to start and end at the same place?

The answers to these questions were first supplied in 1736, by Leonhard Euler, in a paper that proved the first result in what is now known as graph theory. Paths traversing all the bridges (or, in more generality, paths traversing all the edges of the underlying graph) are known as Eulerian paths, and Eulerian paths which start and end at the same place are called Eulerian circuits.

The problem above is known as the Bridges of Konigsberg problem, named after a city in Prussia on the Pregel River with bridges configured as in the picture.

There are four landmasses in the picture. Every path that crosses the bridges will go back and forth between these four landmasses. Suppose there is a person standing on each landmass and watching someone walking the path, counting every time the walker either enters or exits the landmass (including the beginning and end of the path in their count). If there is a path that crosses each bridge exactly once, what will the counters' numbers be when the walker finishes?

The counter on the top will have $3$, since each of the three bridges that hits his landmass will have been crossed exactly once, and each crossing will be counted as either an entry or an exit. Similarly, the counter on the middle island will show $5$, the counter on the right will show $3$, and the counter at the bottom will show $3$.

But the walker enters and exits each landmass every time he passes through, which contributes $2$ to the count, so each counter's final count should be an even number--except for the two counters who count the beginning and the end of the path (the first exit doesn't have a corresponding entry, and the last entry doesn't have a corresponding exit). Still, it's impossible for all four counters to end with odd numbers, so there is no such path.

This problem can be rephrased in terms of graph theory, as follows. Consider the graph with vertices corresponding to the four landmasses, and edges between the vertices corresponding to the bridges. The path in question is a traversal of the graph that passes through each edge exactly once. Or, in other words, it is a drawing of the graph on a piece of paper without picking up our pencil or drawing any edge more than once.

In what follows, graphs will be assumed to be finite (with finitely many vertices and edges). Recall that the degree of a vertex in a graph is the number of edges that touch the vertex.

Here is the graph that corresponds to the bridge problem.

The degree of a vertex corresponding to one of the four landmasses in the original problem is the number that each counter will have in the above proof: the top, right, and bottom vertices have degree $3$ and the left vertex has degree $5$.

An Eulerian path on a graph is a traversal of the graph that passes through each edge exactly once. It is an Eulerian circuit if it starts and ends at the same vertex. $_\square$

The informal proof in the previous section, translated into the language of graph theory, shows immediately that:

If a graph admits an Eulerian path, then there are either $0$ or $2$ vertices with odd degree. If a graph admits an Eulerian circuit, then there are $0$ vertices with odd degree.

The more interesting and difficult statement is the converse. What conditions guarantee the existence of an Eulerian path or Eulerian circuit? It turns out that aside from the necessary conditions on degrees, the only other requirement is the obvious one that any two vertices of degree $\ge 1$ have a path between them.

A graph is connected if there is a path between any two vertices. $_\square$

Every (finite) graph can be uniquely decomposed into connected components: each component is a connected subgraph, and there are no edges between any two components. A vertex of degree zero is its own connected component.

A graph has an Eulerian path if and only if (1) every vertex of degree $\ge 1$ lies in the same connected component, and (2) there are 0 or 2 vertices of odd degree.
A graph has an Eulerian circuit if and only if (1) every vertex of degree $\ge 1$ lies in the same connected component, and (2) every vertex has even degree. $_\square$

Euler stated this theorem without proof when he solved the Bridges of Konigsberg problem in 1736, but the proof was not given until the late $19^\text{th}$ century.

To prove the theorem, the "only if" statements have been established by the above discussion. One way to prove the "if" statements is via the following algorithm due to Fleury which constructs an Eulerian path or circuit.

If there are two vertices of odd degree, start with one of them. Otherwise, start with any vertex. At every step of the algorithm, pick an edge that will not disconnect the graph if it is removed, unless there is no such edge. (Edges that will disconnect the graph if they are removed are--somewhat confusingly in this context--called bridges.) Move along this edge and delete it from the graph once done. Continue.

It can be shown that Fleury's algorithm always produces an Eulerian path, and produces an Eulerian circuit if every vertex has even degree. This uses an important and straightforward lemma known as the handshaking lemma:

Every graph has an even number of vertices with odd degree.

Proof: Every edge hits two vertices, so the sum of the degrees of the vertices equals twice the number of edges. So it is even. The lemma follows immediately.

Rather than giving the details of this proof, here is an alternative algorithm due to Hierholzer that also works. The algorithm produces Eulerian circuits, but it can be modified to produce Eulerian paths if there are two vertices of odd degree.

Suppose every vertex has even degree. Start with a vertex $v$ and follow a path around the graph until it returns to $v$. This will always be possible because there will always be an odd number of unused edges emanating from a vertex that the path has landed on. This produces a circuit that may not be Eulerian; but if it is not, we can start from a vertex $w$ with some unused edges coming from it and follow a path of unused edges around the graph until it returns to $w$. The old circuit plus the new one can be traversed as one large circuit (start at $v$, go to $w$, do the $w$ circuit, continue the rest of the $v$ circuit). Repeat until there are no more unused edges. $\square$

A graph in which all vertices have even degree. ^[1]

Consider the above graph. Starting at vertex 1, draw a circuit 1-2-3-7-1. There are unused edges emanating from vertex 1, so draw another circuit 1-3-4-7-8-1. Put them together to get 1-2-3-7-1-3-4-7-8-1. Now vertex 1 no longer has unused edges, but vertex 4 does: draw 4-5-9-4. Stick this into the previous circuit to get $$1-2-3-7-1-3-{\bf 4-5-9-4}-7-8-1.$$ Finally, vertex 9 has some unused edges left, so draw the circuit 9-6-7-9 and notice that all the edges have been used. Stick it into the previous circuit to get $$1-2-3-7-1-3-4-5-{\bf 9-6-7-9}-4-7-8-1.$$

The Konigsberg bridges have the interesting property that adding or deleting a bridge between any two landmasses will allow an Eulerian path. Indeed, adding or deleting a bridge will change the parity of the degrees of two of the four vertices of the associated graph, which will make them both even. Then there will be two vertices of odd degree, which will imply the existence of an Eulerian path.

This illustrates the power of the theorem; without having to draw the paths in all of the various cases that might arise, nevertheless an affirmative answer can be given to the question of the existence of Eulerian paths.

Another application of the theorem is to the following puzzle:

Suppose five rooms in a house are laid out as follows:

Imagine a door cut into each wall of each room (including the outside). Is there a path that goes through each door exactly once?

---

The answer is no, as the associated graph has four vertices of odd degree. Here are the graphs for the Konigsberg and five-room problems, respectively, with degrees pictured on each vertex.

Note that it is possible in the five-room problem to construct a path that passes through all but one door, but in this case only certain doors can be omitted; the door has to correspond to an edge connecting two odd-degree vertices. $_\square$

1. Tin Tin, C. Hierholzer's algorithm. Retrieved August 8, 2008, from https://commons.wikimedia.org/wiki/File:Hierholzer_(3).png