Lesson 3

An Eulerian path is a route that passes through all edges of a graph exactly once (the word “route” emphasizes that its vertices may be repeated). An Eulerian cycle is an Eulerian path where the first and last vertices coincide.

Theorem. A directed graph without isolated vertices (i.e., vertices of degree zero) contains an Eulerian cycle if and only if it is strongly connected and for every vertex, the in-degree equals the out-degree.

Proof. One direction is simple: if we managed to traverse all edges of the graph, then the graph is strongly connected (recall that there are no isolated vertices) and all degrees are balanced: we entered each vertex as many times as we exited.

Now suppose the graph is strongly connected and all its degrees are balanced. We will construct an Eulerian cycle in this graph. We start at an arbitrary vertex and walk along the edges, each time choosing an edge we have not yet traversed. Due to the balance of all vertices, there is exactly one situation in which this process can stop — when we return to the starting vertex and have no outgoing edges left that we have not yet traversed.

For example, we start from vertex \(a\) and traverse the cycle \(a\to b\to c \to h \to a\).

Returning to our example, we see that vertex \(c\) has such edges. Let us assume that our previous cycle started at \(c\): \[c\to h \to a \to b \to c \ .\] Now we can continue the walk from \(c\)! For example, we traverse the edges \(c \to d \to g \to c\). We obtain the following cycle: \[c\to h \to a \to b \to c \to d \to g \to c \ .\]