Page 726 - Discrete Mathematics and Its Applications

10.5 Euler and Hamilton Paths 705

23. a b c 34. a b c

j
i k
e
d f
o p q
d h
h
g i
n l
m
k
j l
e f g
∗ 24. Devise an algorithm for constructing Euler circuits in di- 35. a b
rected graphs.

25. Devise an algorithm for constructing Euler paths in di- d
rected graphs.
26. For which values of n do these graphs have an Euler cir-
cuit? c e
a) K n b) C n c) W n d) Q n 36. a b c
27. For which values of n do the graphs in Exercise 26 have
an Euler path but no Euler circuit?
d f
e
28. For which values of m and n does the complete bipartite
graph K m,n have an
a) Euler circuit? g h i
b) Euler path?
37. Does the graph in Exercise 30 have a Hamilton path? If
29. Find the least number of times it is necessary to lift a so, find such a path. If it does not, give an argument to
pencil from the paper when drawing each of the graphs show why no such path exists.
in Exercises 1–7 without retracing any part of the graph.
38. Does the graph in Exercise 31 have a Hamilton path? If
In Exercises 30–36 determine whether the given graph has a so, find such a path. If it does not, give an argument to
Hamilton circuit. If it does, find such a circuit. If it does not, show why no such path exists.
give an argument to show why no such circuit exists.
39. Does the graph in Exercise 32 have a Hamilton path? If
so, find such a path. If it does not, give an argument to
30. a d show why no such path exists.

c f 40. Does the graph in Exercise 33 have a Hamilton path? If
so, find such a path. If it does not, give an argument to
show why no such path exists.

b e ∗ 41. Does the graph in Exercise 34 have a Hamilton path? If
so, find such a path. If it does not, give an argument to
31. a b 32. a b show why no such path exists.

42. Does the graph in Exercise 35 have a Hamilton path? If
c so, find such a path. If it does not, give an argument to
c
show why no such path exists.
e d d e f 43. Does the graph in Exercise 36 have a Hamilton path? If
so, find such a path. If it does not, give an argument to
33. a b g show why no such path exists.
44. For which values of n do the graphs in Exercise 26 have
a Hamilton circuit?
45. For which values of m and n does the complete bipartite
graph K m,n have a Hamilton circuit?
e c d f