List the vertices in the tree shown when they are visited in a preorder traversal and in
a postorder traversal.
2 3
4 2 5X6
X7^8
9 10
11 12 13 14
Find an Eulerian circuit in G. Show all steps of the process.
2 3
6 5
G
Topologically sort D.
a b c
g f e d
h
D
6.21.3 Review Questions
Let G = (V, E) be a graph for which deg(v) > r with r > 2 for every v E V. Prove
that G contains a cycle of length at least r + 1. Use this result to show that if everyone
at a party knows at least n others, then it is possible to seat n +^1 of the guests at a
circular table so that everyone know the persons seated on their left and their right.
