Discrete Mathematics for Computer Science

Eulerian Circuits in Directed Graphs 405

Definition 3. Let G be an undirected graph and 0 an orientation for the edges of G. G

is orientable if G with orientation 0 is strongly connected.

In Exercise 9 of Section 6.20, the reader is asked to prove that a directed graph is

orientable if and only if each undirected edge is contained in a cycle. This theorem tells

when a one-way street pattern with each intersection accessible from all other intersections

can be established. The theorem does not tell how good the traffic flow will be. Figure 6.65

shows two examples of orientations that make the graph orientable. Notice, however, that

the directed path from v to w in G is much shorter than the directed path from v to w in H.

V V

G H

Figure 6.65 Two orientations that make a graph orientable.

Eulerian Circuits in Directed Graphs

For a directed graph, we define a directed Eulerian circuit to be a directed circuit that

contains each edge in the graph exactly once. The necessary and sufficient conditions for

a directed graph to have a directed Eulerian circuit can be stated in terms of the indegree

and outdegree of each vertex in the graph

Theorem 1. Let D = (V, E) be a connected digraph. D contains a directed Eulerian

circuit if and only if indeg(v) = outdeg(v) for each v E V.

The proof of this theorem can be constructed by a straightforward modification of the
proof of the necessary and sufficient condition for the existence of an Eulerian circuit in an
undirected graph. The necessary and sufficient condition for the existence of an Eulerian
circuit in the undirected case is that every vertex has even degree. In the Euler Theorem for
directed graphs, this hypothesis translates into the condition that there are as many directed
edges with a vertex as head as there are directed edges with the same vertex as tail. The
adaptation of the proof of the Euler Theorem in the undirected case to the directed case
involves observing that each time the directed Eulerian circuit passes through a vertex, it
accounts for one of the edges contributing to the indegree of the vertex and for one of
the edges contributing to the outdegree of the vertex. Thus, each time an edge is directed
into a vertex in the directed Eulerian circuit, an edge is also directed out of the vertex
and can be used to continue the directed Eulerian circuit-unless this vertex happens to
be the start of the circuit being constructed. In the case of the vertex at the start of the
directed Eulerian circuit, the outdegree contribution from the start vertex is matched with
the indegree contribution of the vertex at the end.