Page 725 - Discrete Mathematics and Its Applications

704 10 / Graphs

6. 15.
b c

i d e
a

h g f
∗ 16. Show that a directed multigraph having no isolated ver-
7. tices has an Euler circuit if and only if the graph is weakly
connectedandthein-degreeandout-degreeofeachvertex
a b c d
are equal.
∗ 17. Show that a directed multigraph having no isolated ver-
tices has an Euler path but not an Euler circuit if and
only if the graph is weakly connected and the in-degree
i h g e f and out-degree of each vertex are equal for all but two
vertices, one that has in-degree one larger than its out-
8. a b c d e degree and the other that has out-degree one larger than
its in-degree.
In Exercises 18–23 determine whether the directed graph
f g h i j
shown has an Euler circuit. Construct an Euler circuit if one
exists. If no Euler circuit exists, determine whether the di-
rected graph has an Euler path. Construct an Euler path if one
exists.
k l m n o
18. a b 19. a b
9. Suppose that in addition to the seven bridges of Königs-
berg (shown in Figure 1) there were two additional
bridges, connecting regions B and C and regions B and
D, respectively. Could someone cross all nine of these
bridges exactly once and return to the starting point?
10. Can someone cross all the bridges shown in this map ex-
actly once and return to the starting point? c d d c
20. a b c

11. When can the centerlines of the streets in a city be painted
d e
without traveling a street more than once? (Assume that
all the streets are two-way streets.)
21. a b c
12. Devise a procedure, similar toAlgorithm 1, for construct-
ing Euler paths in multigraphs.
In Exercises 13–15 determine whether the picture shown can
be drawn with a pencil in a continuous motion without lifting
the pencil or retracing part of the picture.
13. 14. d e

22. a b c

f e d