Euler Cycles in Digraph

As a preliminary result let's establish the following theorem:

A digraph has an Euler cycle if and only if it is connected and the indegree of each vertex equals its outdegree.

(An Euler cycle is a closed path that goes through each edge exactly once.)

Proof

For a proof we may only consider the loopless graphs. (A loop is an edge that starts and ends at the same vertex.) If a graph has an Euler cycle than obviously the number of edges that start at a vertex equals the number of edges that end there.

In the other direction, let G(V, E) be a connected digraph with V as the set of vertices and E the set of edges. If |V| = 1, i.e., there is a single vertex, there is nothing to prove.

Otherwise, start with any vertex, proceed along any outgoing edge, and continue this way until a cycle has been created. (The path can't last indefinitely since E is a finite set of edges. It could not end at a vertex from which there is no way out unless this is where the path has started.)

If the cycle contains all the edges of E of G, we are done. Otherwise, denote the edges of the cycle E', the nodes on it with the outdegree (and hence the indegree) equal to 1 V', and consider the graph G' = G(V - V', E - E'). Since G is connected, the cycle could not be a connected component (unless it's an Euler cycle, which we assumed it is not). If so, every connected component of G' shares at least one vertex with the cycle. Start with those vertices to find a cycle in each of the connected components of G'. Continue in this manner until no edges remain.

Note that the graphs G' obtained on various stages of the construction satisfy the required condition of equality of the in- and outdegree at every vertex. This is so because that is true for G and for every vertex in the cycle.

When finished, the process ends up with a set of cycles with vertices in G whose union contains every edge from E exactly once. To conclude the proof we'll need the following proposition:

The union of a finite number of cycles of a connected (di)graph is a cycle.

The proof is by induction. For a single cycle, there is nothing to prove. If there are more than one, there bound to be at least two that share a vertex. Starting at this vertex we traverse first one of the cycles then the other which exactly implies that the union of the two is a cycle. We are thus able to reduce the number of cycles in the union by 1 which leads to a proof by induction on the number of cycles.

References

V. K. Balakrishnan, Graph Theory, Schaum's Outlines, 1997
Discrete Algorithmic Mathematics, A K Peters, 3^rd edition, 2004.

71534574