Euler Cycles in Digraph
As a preliminary result let's establish the following theorem:
(An Euler cycle is a closed path that goes through each edge exactly once.)
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.
- V. K. Balakrishnan, Graph Theory, Schaum's Outlines, 1997
- Discrete Algorithmic Mathematics, A K Peters, 3rd edition, 2004.
Copyright © 1996-2018 Alexander Bogomolny