The definition of an Euler path extends to directed graphs. Instead of just the degree of a node as the total number of arc ends, we must now keep track of arcs coming into a node and arcs leaving a node. The total number
of arc ends coming into a node is its in-degree; the total number of arc ends leaving a node is its out-degree.
Exercises 17–20 talk about Euler paths in directed graphs.
17. Describe two conditions on a connected directed graph, either of which would guarantee the existence of
an Euler path.
18. Determine whether this graph has an Euler path. If so, list the nodes in such a path.
3
4
2
1
19. Determine whether this graph has an Euler path. If so, list the nodes in such a path.
3
4
2
1
20. Determine whether this graph has an Euler path. If so, list the nodes in such a path.
3
4
2
1
For Exercises 21–28, decide by trial and error whether Hamiltonian circuits exist for the graphs of the given
exercise. If so, list the nodes in such a cycle.
Section 7.2 Euler Path and Hamiltonian Circuit
579
21. Exercise 3
22. Exercise 4
23. Exercise 5
24. Exercise 6
25. Exercise 7
26. Exercise 8
27. Exercise 9
28. Exercise 11
29. Prove that any graph with a Hamiltonian circuit is connected.
30. Find an example of an unconnected graph that has an Euler path. (Hint: Because this seems intuitively
contradictory, you should look for a trivial case.)