22-3 Euler tour

An Euler tour of a strongly connected, directed graph $G = (V, E)$ is a cycle that traverses each edge of $G$ exactly once, although it may visit a vertex more than once.

a. Show that $G$ has an Euler tour if and only if $\text{in-degree}(v) = \text{out-degree}(v)$ for each vertex $v \in V$.

b. Describe an $O(E)$-time algorithm to find an Euler tour of $G$ if one exists. ($\textit{Hint:}$ Merge edge-disjoint cycles.)

a. An Euler tour is a single cycle that traverses each edge of $G$ exactly once, but it might not be a simple cycle. An Euler tour can be decomposed into a set of edge-disjoint simple cycles, however.

If $G$ has an Euler tour, therefore, we can look at the simple cycles that, together, form the tour. In each simple cycle, each vertex in the cycle has one entering edge and one leaving edge. In each simple cycle, therefore, each vertex $v$ has $\text{in-degree}(v) = \text{out-degree}(v)$, where the degrees are either $1$ (if $v$ is on the simple cycle) or $0$ (if $v$ is not on the simple cycle). Adding the in- and out- degrees over all edges proves that if $G$ has an Euler tour, then $\text{in-degree}(v) = \text{out-degree}(v)$ for all vertices $v$.

We prove the converse—that if $\text{in-degree}(v) = \text{out-degree}(v)$ for all vertices $v$, then $G$ has an Euler tour—in two different ways. One proof is nonconstructive, and the other proof will help us design the algorithm for part (b).

First, we claim that if $\text{in-degree}(v) = \text{out-degree}(v)$ for all vertices $v$, then we can pick any vertex $u$ for which $\text{in-degree}(u) = \text{out-degree}(u) \ge 1$ and create a cycle (not necessarily simple) that contains $u$. To prove this claim, let us start by placing vertex $u$ on the cycle, and choose any leaving edge of $u$, say ($u, v$). Now we put $v$ on the cycle. Since $\text{in-degree}(v) = \text{out-degree}(v) \ge 1$, we can pick some leaving edge of $v$ and continue visiting edges and vertices. Each time we pick an edge, we can remove it from further consideration. At each vertex other than $u$, at the time we visit an entering edge, there must be an unvisited leaving edge, since $\text{in-degree}(v) = \text{out-degree}(v)$ for all vertices $v$. The only vertex for which there might not be an unvisited leaving edge is $u$, since we started the cycle by visiting one of $u$'s leaving edges. Since there's always a leaving edge we can visit from all vertices other than $u$, eventually the cycle must return to $u$, thus proving the claim.

The nonconstructive proof proves the contrapositive—that if $G$ does not have an Euler tour, then $\text{in-degree}(v) \ne \text{out-degree}(v)$ for some vertex $v$—by contradiction. Choose a graph $G = (V, E)$ that does not have an Euler tour but has at least one edge and for which $\text{in-degree}(v) = \text{out-degree}(v)$ for all vertices $v$, and let $G$ have the fewest edges of any such graph. By the above claim, $G$ contains a cycle. Let $C$ be a cycle of $G$ with the greatest number of edges, and let $V_C$ be the set of vertices visited by cycle $C$. By our assumption, $C$ is not an Euler tour, and so the set of edges $E' = E - C$ is nonempty. If we use the set $V$ of vertices and the set $E'$ of edges, we get the graph $G' = (V, E')$; this graph has $\text{in-degree}(v) = \text{out-degree}(v)$ for all vertices $v$, since we have removed one entering edge and one leaving edge for each vertex on cycle $C$. Consider any component $G'' = (V'' , E'')$ of $G'$, and observe that $G''$ also has $\text{in-degree}(v) = \text{out-degree}(v)$ for all vertices $v$. Since $E'' \subseteq E' \subsetneq E$, it follows from how we chose $G$ that $G''$ must have an Euler tour, say $C'$. Because the original graph G is connected, there must be some vertex $x \in V'' \cup V_C$ and, without loss of generality, consider $x$ to be the first and last vertex on both $C$ and $C'$. But then the cycle $C''$ formed by first traversing $C$ and then traversing $C'$ is a cycle of $G$ with more edges than $C$, contradicting our choice of $C$. We conclude that $C$ must have been an Euler tour.

The constructive proof uses the same ideas. Let us start at a vertex $u$ and, via random traversal of edges, create a cycle. We know that once we take any edge entering a vertex $v \ne u$, we can find an edge leaving $v$ that we have not yet taken. Eventually, we get back to vertex $u$, and if there are still edges leaving $u$ that we have not taken, we can continue the cycle. Eventually, we get back to vertex $u$ and there are no untaken edges leaving $u$. If we have visited every edge in the graph $G$, we are done. Otherwise, since $G$ is connected, there must be some unvisited edge leaving a vertex, say $v$, on the cycle. We can traverse a new cycle starting at $v$, visiting only previously unvisited edges, and we can splice this cycle into the cycle we already know. That is, if the original cycle is $\langle u, \ldots, v, w, \ldots, u \rangle$, and the new cycle is $\langle v, x, \ldots, v\rangle$, then we can create the cycle $\langle u, \ldots, v, x, \ldots, v, w, \ldots, u \rangle$. We continue this process of finding a vertex with an unvisited leaving edge on a visited cycle, visiting a cycle starting and ending at this vertex, and splicing in the newly visited cycle, until we have visited every edge.

b. The algorithm is based on the idea in the constructive proof above.

We assume that $G$ is represented by adjacency lists, and we work with a copy of the adjacency lists, so that as we visit each edge, we can remove it from its adjacency list. The singly linked form of adjacency list will suffice. The output of this algorithm is a doubly linked list $T$ of vertices which, read in list order, will give an Euler tour. The algorithm constructs $T$ by finding cycles (also represented by doubly linked lists) and splicing them into $T$. By using doubly linked lists for cycles and the Euler tour, splicing a cycle into the Euler tour takes constant time.

We also maintain a singly linked list $L$, in which each list element consists of two parts:

  1. a vertex $v$, and
  2. a pointer to some appearance of $v$ in $T$.

Initially, $L$ contains one vertex, which may be any vertex of $G$.

Here is the algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
EULER-TOUR(G)
    T = empty list
    L = (any vertex v  G.V, NIL)
    while L is not empty
        remore (v, location - in-T) from L
        C = VISIT(G, L, v)
        if location - in-T == NIL
            T = C
        else splice C into T just before location - in-T
    return T
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
VISIT(G, L, v)
    C = empty sequence of vertices
    u = v
    while out-degree(u) > 0
        let w be the first vertex in G.Adj[u]
        remove w from G.Adj[u], decrementing out-degree(u)
        add u onto the end of C
        if out-degree(u) > 0
            add (u, u's location in C) to L
        u = w
    return C

The use of $\text{NIL}$ in the initial assignment to $L$ ensures that the first cycle $C$ returned by $\text{VISIT}$ becomes the current version of the Euler tour $T$. All cycles returned by $\text{VISIT}$ thereafter are spliced into $T$. We assume that whenever an empty cycle is returned by $\text{VISIT}$, splicing it into $T$ leaves $T$ unchanged.

Each time that $\text{EULER-TOUR}$ removes a vertex $v$ from the list $L$, it calls $\text{VISIT}(G, L, v)$ to find a cycle $C$, possibly empty and possibly not simple, that starts and ends at $v$; the cycle $C$ is represented by a list that starts with $v$ and ends with the last vertex on the cycle before the cycle ends at $v$. $\text{EULER-TOUR}$ then splices this cycle $C$ into the Euler tour $T$ just before some appearance of $v$ in $T$.

When $\text{VISIT}$ is at a vertex $u$, it looks for some vertex $w$ such that the edge $(u, w)$ has not yet been visited. Removing $w$ from $Adj[u]$ ensures that we will never visit $(u, w)$ again. $\text{VISIT}$ adds $u$ onto the cycle $C$ that it constructs. If, after removing edge $(u, w)$, vertex $u$ still has any leaving edges, then $u$, along with its location in $C$, is added to $L$. The cycle construction continues from $w$, and it ceases once a vertex with no unvisited leaving edges is found. Using the argument from part (a), at that point, this vertex must close up a cycle. At that point, therefore, the cycle $C$ is returned.

It is possible that a vertex $u$ has unvisited leaving edges at the time it is added to list $L$ in $\text{VISIT}$, but that by the time that $u$ is removed from $L$ in $\text{EULER-TOUR}$, all of its leaving edges have been visited. In this case, the while loop of $\text{VISIT}$ executes $0$ iterations, and $\text{VISIT}$ returns an empty cycle.

Once the list $L$ is empty, every edge has been visited. The resulting cycle $T$ is then an Euler tour.

To see that $\text{EULER-TOUR}$ takes $O(E)$ time, observe that because we remove each edge from its adjacency list as it is visited, no edge is visited more than once. Since each edge is visited at some time, the number of times that a vertex is added to $L$, and thus removed from $L$, is at most $|E|$. Thus, the while loop in $\text{EULER-TOUR}$ executes at most $E$ iterations. The while loop in $\text{VISIT}$ executes one iteration per edge in the graph, and so it executes at most $E$ iterations as well. Since adding vertex $u$ to the doubly linked list $C$ takes constant time and splicing $C$ into $T$ takes constant time, the entire algorithm takes $O(E)$ time.