# 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.

- Graphs Fundamentals
- Crossing Number of a Graph
- Regular Polyhedra
- 3 Utilities Puzzle: Water, Gas, Electricity
- A Clique of Acquaintances
- Round Robin Tournament
- The Affirmative Action Problem
- The Two Men of Tibet Problem
- Euler Cycles in Digraph
- Fleury's Algorithm and Euler's Paths and Cycles: an Interactive Gizmo
- Graph with Nodes of Even Degree
- Graph without 3-Cycles

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

Copyright © 1996-2018 Alexander Bogomolny

63241137 |