Page 710 - Discrete Mathematics and Its Applications

10.4 Connectivity 689

there are exactly eight paths of length four from a to d. By inspection of the graph, we see that
a, b, a, b, d; a, b, a, c, d; a, b, d, b, d; a, b, d, c, d; a, c, a, b, d; a, c, a, c, d; a, c, d, b, d; and
a, c, d, c, d are the eight paths of length four from a to d. ▲

Theorem 2 can be used to find the length of the shortest path between two vertices of a
graph (see Exercise 56), and it can also be used to determine whether a graph is connected (see
Exercises 61 and 62).

Exercises

1. Does each of these lists of vertices form a path in the 6. How many connected components does each of the
following graph? Which paths are simple? Which are cir- graphs in Exercises 3–5 have? For each graph find each
cuits? What are the lengths of those that are paths? of its connected components.
a) a, e, b, c, b b) a, e, a, d, b, c, a
7. What do the connected components of acquaintanceship
c) e, b, a, d, b, e d) c, b, d, a, e, c
graphs represent?
a b c 8. What do the connected components of a collaboration
graph represent?
9. Explainwhyinthecollaborationgraphofmathematicians
(see Example 3 in Section 10.1) a vertex representing a
mathematician is in the same connected component as the
d e vertex representing Paul Erd˝os if and only if that mathe-
matician has a finite Erd˝os number.
2. Does each of these lists of vertices form a path in the 10. In the Hollywood graph (see Example 3 in Section 10.1),
following graph? Which paths are simple? Which are cir- when is the vertex representing an actor in the same con-
cuits? What are the lengths of those that are paths? nected component as the vertex representing Kevin Ba-
a) a, b, e, c, b b) a, d, a, d, a con?
c) a, d, b, e, a d) a, b, e, c, b, d, a
11. Determine whether each of these graphs is strongly con-
nected and if not, whether it is weakly connected.
a b c

a) a b c

d e

In Exercises 3–5 determine whether the given graph is con- e d
nected.

b) a b
3.

c

4.
e d

c) b
5.
a c

g d
f e