Chapter Review
415
degree value. (Hint: If I V I is even, then the repeated degree can have two possible
values. If I V I is odd, then the repeated value is unique.)
9. Prove that a graph is connected if and only if every two-part partition of the vertices
of the graph has an edge with ends in both parts of the partition.
10. Using the picture of the bridges connecting the two islands in the middle of the Seine
in Paris, describe a trail that takes you over each bridge exactly once. See the comment
about multigraphs in Section 6.8.
a
b
c
dfg
3
0
nmlI
k
i
h
4
Paris bridges joining the islands in the Seine.
11. Prove that if a tree has a vertex of degree p, then it has at least p vertices of degree
one.
12. Agents A, B, C, D, E, F G, and H are embroiled in a conspiracy called the Bucknellgate Affair. To coordinate their cover-up efforts, each conspirator must be able to communicate with each other either directly or indirectly (through another conspirator).
A table of risk factors is given for each possible direct communication link. What
is the least total possible risk while still meeting the requirements for communication?
Agent
A A A A A B B C C C C D D E
Pairs
B C E F G C F D F G H E H H
Risk
Factor 6 3 7 4 13 6 5 4
6 7
9 2
8 5
13. Prove that D 1 and D 2 are not isomorphic.
2
50
a
e