Chapter Review
413
8. 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
9. Find an Eulerian circuit in G. Show all steps of the process.
2
3
6
5
G
10. Topologically sort D.
a
b
c
g
f
e
d
h
D
6.21.3 Review Questions
1. 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.
413
8. 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
9. Find an Eulerian circuit in G. Show all steps of the process.
2
3
6
5
G
10. Topologically sort D.
a
b
c
g
f
e
d
h
D
6.21.3 Review Questions
1. 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.