# 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

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

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.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny