Chapter Review 415degree 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.)- 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. - 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 dfg30 nmlI k i h
4
Paris bridges joining the islands in the Seine.- 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 Bucknell-
gate Affair. To coordinate their cover-up efforts, each conspirator must be able to com-
municate 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 communica-
tion?Agent A A A A A B B C C C C D D EPairs B C E F G C F D F G H E H H
RiskFactor (^6 3 7 4 13 6 5 4 6 7 9 2 8 5)
- Prove that D 1 and D 2 are not isomorphic.
(^2 50)
a e