Eulerian Graphs

Section 5.3 Eulerian Graphs

Objectives

Define Eulerian graphs; determine whether a given graph is Eulerian or not. Explain how degree sequences allow us to do this.

Video: Eulerian Graphs

In the previous section we defined the degree of a vertex and proved some properties about degree sequences. We can use vertex degrees to answer the five-room problem in Example 5.1.1 in the negative. First, we need a few more definitions.

🔗

Definition 5.3.1. Trail.

A trail in a graph $G = (v, E)$ is an alternating list of vertices and edges

u_{0}, e_{0}, u_{1}, e_{1}, u_{2}, \dots, e_{k - 1}, u_{k}

such that each edge $e_{i}$ has $u_{i}$ and $u_{i + 1}$ as its endpoints, and that these $e_{i}$ 's are distinct (for $i = 0, 2, \dots, k - 1$ ). A trail is said to be closed if its endpoints $u_{0}$ and $u_{k}$ are the same vertex.

🔗

Note that for simple graphs we can just write a list of vertices to describe the trail since there are no multiple edges between any two vertices.

🔗

Example 5.3.2. A Trail.

The graph $G$ contains the trail 1-2-6-7-3-2, denoted by the thick red edges. It is not closed. Also, it cannot be continued to make it closed because one of the edges $(1,2)$ or $(2,6)$ would have to be repeated for the trail to make its way back to vertex $1\text{.}$

🔗

Definition 5.3.3. Eulerian Graph.

A graph is said to be Eulerian if it has a closed trail containing all its edges. This trail is called an Eulerian trail.

🔗

The condition of having a closed trail that uses all the edges of a graph is equivalent to saying that the graph can be drawn on paper in one motion without lifting one's pen.

🔗

Example 5.3.4. Eulerian and non-Eulerian Graphs.

The graph $H_1$ below is Eulerian since the closed trail 3-1-2-3-4-5-3 uses all its edges exactly once.

However the graph $H_2$ is not Eulerian. Although it contains trails (e.g., 4-3-2-5-4-2-1-3-5) that use all its edges exactly once, none of these are closed trails.

🔗

It turns out that there is an easy way to tell whether a graph is Eulerian or not. Intuitively, to be able to draw an Eulerian trail on a graph, we should always be able to leave any vertex we land on, unless it is the starting vertex. Also, the graph has to be in ‘one piece’, otherwise no trail can contain all edges. This leads to our next two definitions (we will discuss these in more detail in Section 5.5).

🔗

Definition 5.3.5. Path.

A path is a trail in which no vertices are repeated (so it is not closed). The endpoints of a trail are the first and last vertices. A path with endpoints $u$ and $v$ is called a $u$ - $v$ path.

🔗

Definition 5.3.6. Connectedness.

A graph $G = (V, E)$ is said to be connected if for all $u, v \in V (G),$ there is a $u$ - $v$ path joining them.

A graph that is not connected is called disconnected.

🔗

Example 5.3.7. A Disconnected Graph.

The graph below is disconnected, since there is no path on the graph with endpoints $1$ and $6$ (among other choices).

🔗

Now we can state a necessary and sufficient condition for a graph to be Eulerian.

🔗

Theorem 5.3.8. When is a Graph Eulerian?

A (not necessarily simple) graph $G$ is Eulerian if and only if

all its vertex degrees are even, and
$G$ is connected.

🔗

Proof.

We first show the only if implication. Suppose $G$ is a (not necessarily simple) Eulerian graph. Then there is a closed trail in $G\text{,}$ say

\begin{equation*} u_0, e_0, u_1, e_1, \ldots, e_{k-1}, u_k = u_0 \end{equation*}

that traverses all the edges of $G$ exactly once. (Some of the $u_i$'s may be repeated, but none of the edges are repeated.)

For each vertex in $V(G)\text{,}$ each time it appears in this list (say as $u_i$), the trail passes through it and we add two to its degree (one from $e_{i-1} = (u_{i-1},u_i)$ and one from $e_i = (u_i,u_{i+1})$). This is true even for $u_0$ since we also add two to its degree for the first and last edge of the trail, which comes back to $u_k = u_0\text{.}$

Hence all vertex degrees must be even. The graph $G$ must also be connected if it contains an Eulerian trail. This shows the only if direction.

The if implication is better explained by the following algorithm:

Suppose $G$ is a graph whose vertices all have even degree, and also assume that every vertex is reachable from every other vertex. We will construct an Eulerian trail on $G\text{.}$

Step 1.: Choose any vertex $v$ of $G\text{,}$ and create a trail that starts and ends at $v\text{,}$ never repeating an edge.
Step 2.: Call this trail $C\text{.}$
Step 3.: If $C$ is all of $G\text{,}$ then we are done, and we have found an Eulerian trail in $G\text{.}$
Step 4.: If not, then remove the edges of $C$ from $G$ to form a new graph $G'\text{.}$ Since $C$ is a closed trail, removing it reduces each vertex degree of $G$ by an even number, so $G'$ also has all vertex degrees even.
Step 5.: Choose a vertex $v'$ common to $C$ and $G'\text{,}$ and create a trail in $G'$ that starts and ends at $v'\text{.}$ Call this new trail $C'\text{.}$
Step 6.: Combine $C$ and $C'$ to get a new trail $C''$ by inserting $C'$ where the vertex $v'$ occurs in $C\text{.}$ Now set $C = C''$ and go back to Step 2.

The above algorithm constructs an Eulerian trail on $G$ by first finding a closed trail $C\text{,}$ then finding another trail $C'$ through the remaining edges, and finally combining both trails by inserting $C'$ at the vertex $v'$ in trail $C\text{.}$

🔗

Example 5.3.9. Solution to the Five-Room Problem.

Now we can finally resolve Example 5.1.1. Whether or not one can walk through all the walls of the building exactly once and return to the same room is equivalent to asking whether the graph of Example 5.1.2 contains an Eulerian trail or not. The answer here is no, since the graph has vertices of odd degree.

🔗

Example 5.3.10. Disconnected, so not Eulerian.

The vertices of the graph below all have even degree. However the graph is not Eulerian since it is disconnected.

🔗

Checkpoint 5.3.11. Find Eulerian Trails.

Verify that all vertex degrees of $G_1\text{,}$ $G_2\text{,}$ and $G_3$ are even, then find an Eulerian trail in each graph. (Note that $G_3$ is a multigraph.)

🔗

We end this section by defining some special graphs.

🔗

Definition 5.3.12. Cycle.

A cycle is a closed trail in which only the first and last vertices are repeated.

The cycle graph with $n$ vertices is denoted by $C_{n},$ and is a graph that consists of a single cycle.

🔗

Definition 5.3.13. Complete Graph.

The complete graph on $n$ vertices is denoted by $K_{n},$ and is the simple graph on $n$ vertices that consists of all possible edges between all vertex pairs.

🔗

Example 5.3.14. Examples.

Here are the graphs of $C_4\text{,}$ $C_5\text{,}$ $K_4\text{,}$ and $K_5$ (from left to right).

🔗

Checkpoint 5.3.15. Compute $| E (K_{n}) |$ .

Determine $|E(K_n)|\text{,}$ the number of edges of the complete graph on $n$ vertices.

🔗

Checkpoint 5.3.16. Are $C_{n}$ and $K_{n}$ Eulerian?

Determine the degree sequences of $C_n$ and $K_n$ for any $n \in \mathbb{N}\text{.}$ Then show that the graph $C_n$ is Eulerian for all $n \in \mathbb{N}\text{,}$ while the complete graph $K_n$ is Eulerian only for odd $n \in \mathbb{N}\text{.}$

🔗

Checkpoint 5.3.17. Find Eulerian Trails on $K_{5}$ and $K_{7}$ .

Find an Eulerian trail on each of $K_5$ and on $K_7\text{.}$