Skip to main content

Section 3.1 Euler Tours

Definition 3.1.1.

The idea is this: we would like to know when it is possible to trace over every edge in a graph exactly once, without lifting our pencil. We should be careful about what this “tracing” actually is.

A walk in a graph \(G = (V,E)\) is a sequence of vertices \(v_0, v_1, v_2, \ldots, v_n\) such that \(\{v_i, v_{i+1}\} \in E\) for all \(0 \le i \lt n\text{.}\) That is, consecutive vertices in the sequence are adjacent in the graph.

A trail is a walk that does not repeat any edges. If the trail starts and ends at the same vertex (i.e., \(v_1 = v_n\)) then it is called a circuit

A path is a trail that does not repeat any vertices, except perhaps for \(v_0 = v_n\text{.}\) In the case that \(v_0 = v_n\text{,}\) the path is called a cycle.

Does the definition of path above agree with the one we have considered previously?

Definition 3.1.2.

A walk in a graph that uses every edge exactly once is called an Euler trail. An Euler tour that starts and ends at the same vertex is called an Euler tour.

Note that an Euler trail is sometimes also called an Euler walk or Euler path, and that an Euler tour is also called an Euler circuit. We say that graphs which possess and Euler tour are Eulerian.

It would be nice to find a necessary and sufficient condition for a graph to be Eulerian.

Activity 12.
(a)

Which of the graphs/multigraphs below have Euler trails? Which have Euler tours?

(b)

Is it possible for a graph with a degree 1 vertex to have an Euler tour? If so, draw one. If not, explain why not. What about an Euler trail?

(c)

What if every vertex of the graph has degree 2. Is there an Euler trail? An Euler tour? Draw some graphs.

(d)

Below is part of a graph. Even though you can only see some of the vertices, can you deduce whether the graph will have an Euler trail or tour?

(e)

Incorporating everything you have uncovered above, conjecture a necessary condition (or conditions) for a graph being Eulerian.

Consider the sequence of vertices \(\{v_0, v_1,...,v_{n-1}, v_n,v_0\}\) where the vertices are not necessarily distinct.

There must exist an edge between each pair of adjacent vertices in our sequence. Thus for each occurrence of a distinct vertex in our sequence, there are two edges connected to that vertex. So the number of edges, or equivalently the degree of each vertex, must be a multiple of two.

The necessary condition above is, upon reflection, obvious. What is something that would definitely prevent you from forming an Euler tour? if you had a vertex that had an odd number of edges incident to it. Could it possibly be that this obvious necessary condition is the only obstruction to a graph being Eulerian? That is, is the necessary condition also sufficient?

In Theorem 3.1.3 we proved that if a connected graph has an Euler tour, then every vertex has even degree. Thus we need only prove the converse here. We will proceed by induction.

Base case: Suppose that every vertex has even degree. Notice that the this means the minimum degree must be 2. Using Proposition 1.3.5, either we have a cycle (because the minimum degree is greater than 2), or every vertex had degree two, then the graph is a cycle that uses every vertex (hence an Euler tour) and we are done.

Suppose the graph has every vertex with even degree, but no Euler tour. We showed above that the graph must have a cycle, so consider the subgraph \(G'\) that is \(G\) with the edges of this cycle removed. Then each of the connected components of \(G'\) must have all even degree. So by Proposition 1.3.5 they must also have a cycle. If we add back in the cycle, then we can create the Euler tour by starting at a vertex of our cycle. If the vertex has degree greater than 2, then we can follow the cycle that is not a part of our original cycle until we reconnect at that vertex. Then we can continue along the cycle in this way until we reach our original vertex. By following all the cycles, we ensure we have traversed every edge of the graph and therefore have an Euler tour.

What about Euler trails? Since every tour is also a trail, all Eulerian graphs have Euler trails. But there are definitely graphs that have some odd degree vertices that still have Euler trails (for example, any path).

By Theorem 3.1.4, we know every connected graph with an Euler Tour every vertex of even degree.

Forward direction: suppose \(G\) is a connected graph with an Euler trail. Thus there exists a walk that uses every edge exactly once. If the walk starts and ends at the same vertex then it is an Euler tour and so every vertex will have even degree, and therefore no vertices of odd degree. If the Euler trail is not also a tour, then at least one vertex has odd degree by Theorem 3.1.4. Consider starting your Euler Trail at the odd vertex. If this vertex is of odd degree, the Euler trail leaves the vertex and must go through vertices of even degrees and end at an odd vertex. If not the trail would not be Euler, since it would either not include all the edges or would use an edge twice since a vertex would lack the inbound edge and an outbound edge. Thus if a graph is an Euler trail, it has \(0\) or \(2\) vertices of odd degree.

Backward direction: suppose \(G\) is a connected graph with only 0 or 2 vertices of odd degree. If \(G\) has zero vertices of odd degree, then by Theorem 3.1.3, \(G\) has an Euler Tour and thus an Euler Trail. If \(G\) has only two vertices of odd degree, \(v_1, v_2\text{,}\) then we can add a vertex \(v_0\) to the graph with two edges such that the new vertex is adjacent to the two odd degree vertices, \(v_1\) and \(v_2\text{.}\) Then every vertex has even degree so by Theorem 3.1.4, the resulting graph has a Euler tour. Let the tour begin and end at \(v_1\text{.}\) Then if we remove \(v_0\text{,}\) the original graph has an Euler trail from \(v_1\) to \(v_2\text{.}\) Thus a connected graph with only 0 or 2 vertices of odd degree has a Euler Trail.

While it would be relatively straight forward to prove the previous theorem directly, using a similar argument as the proof of Theorem 3.1.4, we instead could try to use Theorem 3.1.4 directly. To do this, we need to translate between the hypotheses and conclusions of the two theorems. In fact, we can prove that the two theorems are equivalent in this way.

Before leaving Euler tours, here is a nice application to consider. A graph in which every vertex has degree \(k\) is called \(k\)-regular. A \(k\)-regular spanning subgraph is called a \(k\)-factor.

Let \(G \) be a 4-regular graph. Consider if \(G \) is connected. Then, by Theorem 3.1.4 \(G \) has an Euler tour. The Euler tour would use exactly 2 edges from each vertex and every vertex and this is itself a 2-factor, so consider the subgraph, \(G' \text{,}\) induced by removing all the edges from the Euler tour. The vertex set of \(G \) equals the vertex set of \(G'\) because we only removed edges to create \(G'\text{.}\) Because we removed exactly 2 edges from each vertex, each vertex now has 2 edges. Thus, \(G' \) is a 2-factor. Therefore, \(G \) was decomposed into two 2-factors. If G was not connected, then we can do this process for each connected subgraph of \(G \text{.}\)