Eulerian Digraphs
Table of Contents

Eulerian Digraphs

Definition: A digraph $D$ is Eulerian if it contains a closed trail (a walk containing no repeated arcs) that contains all of the arcs in $D$. This closed trail is known as an Eulerian Trail.

Essentially, the same conditions for regular graphs being Eulerian hold for digraphs being Eulerian, however, we are now regarding Eulerian trails with regards to arcs. For example, the following digraph is Eulerian:

Screen%20Shot%202014-04-10%20at%202.27.37%20PM.png

We should also not that the underlying graph being Eulerian does not imply that a digraph with that underlying graph is Eulerian. For example, the following orientation of the arcs of the graph above no longer make $D$ Eulerian:

Screen%20Shot%202014-04-10%20at%202.33.12%20PM.png

This is because we must start our trail at vertex $a$ and end at vertex $a$. This is of course, impossible, since the in-degree of vertex $a$ is $0$.

Theorem 1: A connected digraph is Eulerian if and only if the in-degree of each vertex equals the out-degree of each vertex.

We will not prove this theorem, however we should note that if the in-degree does not equal the out-degree, then at some point in our Eulerian trail we will either be "stuck" at a vertex, as in there will be no more available arcs to traverse that haven't already been traversed OR "trapped" at a vertex.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License