Page 718 - Discrete Mathematics and Its Applications

10.5 Euler and Hamilton Paths 697

a j
e i
f
b h
d g
c k
G
FIGURE 6 Mohammed’s Scimitars.

EXAMPLE 3 Many puzzles ask you to draw a picture in a continuous motion without lifting a pencil so that
no part of the picture is retraced. We can solve such puzzles using Euler circuits and paths.
For example, can Mohammed’s scimitars, shown in Figure 6, be drawn in this way, where the
drawing begins and ends at the same point?

Solution: We can solve this problem because the graph G shown in Figure 6 has an Euler circuit.
It has such a circuit because all its vertices have even degree.We will useAlgorithm 1 to construct
an Euler circuit. First, we form the circuit a, b, d, c, b, e, i, f, e, a. We obtain the subgraph H
by deleting the edges in this circuit and all vertices that become isolated when these edges are
removed. Then we form the circuit d, g, h, j, i, h, k, g, f, d in H. After forming this circuit we
have used all edges in G. Splicing this new circuit into the first circuit at the appropriate place
produces the Euler circuit a, b, d, g, h, j, i, h, k, g, f, d, c, b, e, i, f, e, a. This circuit gives a
way to draw the scimitars without lifting the pencil or retracing part of the picture. ▲

Another algorithm for constructing Euler circuits, called Fleury’s algorithm, is described in
the premble to Exercise 50.
We will now show that a connected multigraph has an Euler path (and not an Euler circuit) if
and only if it has exactly two vertices of odd degree. First, suppose that a connected multigraph
does have an Euler path from a to b, but not an Euler circuit. The first edge of the path contributes
one to the degree of a. A contribution of two to the degree of a is made every time the path
passes through a. The last edge in the path contributes one to the degree of b. Every time the
path goes through b there is a contribution of two to its degree. Consequently, both a and b have
odd degree. Every other vertex has even degree, because the path contributes two to the degree
of a vertex whenever it passes through it.
Now consider the converse. Suppose that a graph has exactly two vertices of odd degree,
say a and b. Consider the larger graph made up of the original graph with the addition of an
edge {a, b}. Every vertex of this larger graph has even degree, so there is an Euler circuit. The
removal of the new edge produces an Euler path in the original graph. Theorem 2 summarizes
these results.

THEOREM 2 A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly
two vertices of odd degree.

EXAMPLE 4 Which graphs shown in Figure 7 have an Euler path?

Solution: G 1 contains exactly two vertices of odd degree, namely, b and d. Hence, it has an Euler
path that must have b and d as its endpoints. One such Euler path is d, a, b, c, d, b. Similarly, G 2
has exactly two vertices of odd degree, namely, b and d. So it has an Euler path that must have
b and d as endpoints. One such Euler path is b, a, g, f, e, d, c, g, b, c, f, d. G 3 has no Euler
path because it has six vertices of odd degree. ▲
Returning to eighteenth-century Königsberg, is it possible to start at some point in the
town, travel across all the bridges, and end up at some other point in town? This question can