Page 712 - Discrete Mathematics and Its Applications

10.4 Connectivity 691

22. Use paths either to show that these graphs are not isomor- 34. Find all the cut edges in the graphs in Exercises 31–33.
phic or to find an isomorphism between them.
∗ 35. Suppose that v is an endpoint of a cut edge. Prove that v
u 1 u 2 v 1 v 2 is a cut vertex if and only if this vertex is not pendant.

∗ 36. Show that a vertex c in the connected simple graph G is
u 8 u 3 v 8 v 3
a cut vertex if and only if there are vertices u and v, both
different from c, such that every path between u and v
u 7 u 4 v 7 v 4
passes through c.
u 6 u 5 v 6 v 5 ∗ 37. Show that a simple graph with at least two vertices has at
G H least two vertices that are not cut vertices.
23. Use paths either to show that these graphs are not isomor-
∗ 38. Show that an edge in a simple graph is a cut edge if and
phic or to find an isomorphism between them.
only if this edge is not part of any simple circuit in the
u 1 u 2 v 1 graph.
u 6 u 7 v 39. A communications link in a network should be provided
v 5 6
v 4 v 2 with a backup link if its failure makes it impossible for
v 7
u 8 u 3 v 8 some message to be sent. For each of the communications
networks shown here in (a) and (b), determine those links
u 5 u 4 v 3 that should be backed up.
G H a) Boston
24. Find the number of paths of length n between any two ad- Chicago
jacent vertices in K 3,3 for the values of n in Exercise 19. New York
San Francisco
25. Find the number of paths of length n between any two Denver Washington
nonadjacent vertices in K 3,3 for the values of n in Exer-
cise 19. Los Angeles
26. Find the number of paths between c and d in the graph in
b) Bangor
Figure 1 of length Burlington
Seattle Portland
a) 2. b) 3. c) 4. d) 5. e) 6. f) 7.
Boston
27. Find the number of paths from a to e in the directed graph San Denver Chicago
in Exercise 2 of length Francisco New York
Washington
Kansas City
a) 2. b) 3. c) 4. d) 5. e) 6. f) 7.
Salt Lake Atlanta
∗ 28. Show that every connected graph with n vertices has at Los City
least n − 1 edges. Angeles
29. Let G = (V, E) be a simple graph. Let R be the relation
A vertex basis in a directed graph G is a minimal set B of
on V consisting of pairs of vertices (u, v) such that there
vertices of G such that for each vertex v of G not in B there
is a path from u to v or such that u = v. Show that R is
is a path to v from some vertex B.
an equivalence relation.
∗ 30. Show that in every simple graph there is a path from every 40. Find a vertex basis for each of the directed graphs in Ex-
vertex of odd degree to some other vertex of odd degree. ercises 7–9 of Section 10.2.
In Exercises 31–33 find all the cut vertices of the given graph.
41. What is the significance of a vertex basis in an influence
31. a d e 32. a f graph (described in Example 2 of Section 10.1)? Find a
vertex basis in the influence graph in that example.
42. Show that if a connected simple graph G is the union of
b c d e the graphs G 1 and G 2 , then G 1 and G 2 have at least one
b c f
common vertex.
33. a b f
∗ 43. Show that if a simple graph G has k connected compo-
nents and these components have n 1 ,n 2 ,...,n k vertices,
respectively, then the number of edges of G does not ex-
e
c g
ceed
k

C(n i , 2).
d i h i=1