Page 715 - Discrete Mathematics and Its Applications

694 10 / Graphs

The problem of traveling across every bridge without crossing any bridge more than once
can be rephrased in terms of this model. The question becomes: Is there a simple circuit in this
multigraph that contains every edge?

DEFINITION 1 An Euler circuit in a graph G is a simple circuit containing every edge of G.An Euler path
in G is a simple path containing every edge of G.

Examples 1 and 2 illustrate the concept of Euler circuits and paths.
EXAMPLE 1 Which of the undirected graphs in Figure 3 have an Euler circuit? Of those that do not, which
have an Euler path?

Solution: The graph G 1 has an Euler circuit, for example, a, e, c, d, e, b, a. Neither of the
graphs G 2 or G 3 has an Euler circuit (the reader should verify this). However, G 3 has
an Euler path, namely, a, c, d, e, b, d, a, b. G 2 does not have an Euler path (as the reader
should verify). ▲

EXAMPLE 2 Which of the directed graphs in Figure 4 have an Euler circuit? Of those that do not, which have
an Euler path?

Solution: The graph H 2 has an Euler circuit, for example, a, g, c, b, g, e, d, f, a. Neither H 1
nor H 3 has an Euler circuit (as the reader should verify). H 3 has an Euler path, namely,
c, a, b, c, d, b,but H 1 does not (as the reader should verify). ▲

NECESSARY AND SUFFICIENT CONDITIONS FOR EULER CIRCUITS AND PATHS
There are simple criteria for determining whether a multigraph has an Euler circuit or an Euler
path. Euler discovered them when he solved the famous Königsberg bridge problem. We will
assume that all graphs discussed in this section have a finite number of vertices and edges.
What can we say if a connected multigraph has an Euler circuit? What we can show is that
every vertex must have even degree. To do this, first note that an Euler circuit begins with a
vertex a and continues with an edge incident with a, say {a, b}. The edge {a, b} contributes one
to deg(a). Each time the circuit passes through a vertex it contributes two to the vertex’s degree,
because the circuit enters via an edge incident with this vertex and leaves via another such edge.
Finally, the circuit terminates where it started, contributing one to deg(a). Therefore, deg(a)
must be even, because the circuit contributes one when it begins, one when it ends, and two
every time it passes through a (if it ever does). A vertex other than a has even degree because
the circuit contributes two to its degree each time it passes through the vertex. We conclude that
if a connected graph has an Euler circuit, then every vertex must have even degree.
Is this necessary condition for the existence of an Euler circuit also sufficient? That is, must
an Euler circuit exist in a connected multigraph if all vertices have even degree? This question
can be settled affirmatively with a construction.

a b
a b a b a b a b c d
g
e e f c

d c d c c d e d c a b
e d
G 1 G 2 G 3 H 1 H 2 H 3

FIGURE 3 The Undirected Graphs G 1 , G 2 , and G 3 . FIGURE 4 The Directed Graphs H 1 , H 2 , and H 3 .