Page 713 - Discrete Mathematics and Its Applications

692 10 / Graphs

∗ 44. Use Exercise 43 to show that a simple graph with n 53. Find κ(K m,n ) and λ(K m,n ), where m and n are positive
vertices and k connected components has at most (n − integers.
k)(n − k + 1)/2 edges. [Hint: First show that
54. Construct a graph G with κ(G) = 1, λ(G) = 2, and
k min v∈V deg(v) = 3.
2 2
n ≤ n − (k − 1)(2n − k),
i ∗ 55. Show that if G is a graph, then κ(G) ≤ λ(G).
i=1
56. Explain how Theorem 2 can be used to find the length of
where n i is the number of vertices in the ith connected the shortest path from a vertex v to a vertex w in a graph.
component.]
57. Use Theorem 2 to find the length of the shortest path
∗ 45. Show that a simple graph G with n vertices is connected
between a and f in the graph in Figure 1.
if it has more than (n − 1)(n − 2)/2 edges.
58. Use Theorem 2 to find the length of the shortest path from
46. Describe the adjacency matrix of a graph with n con- a to c in the directed graph in Exercise 2.
nected components when the vertices of the graph are
listed so that vertices in each connected component are 59. Let P 1 and P 2 be two simple paths between the vertices u
listed successively. and v in the simple graph G that do not contain the same
set of edges. Show that there is a simple circuit in G.
47. How many nonisomorphic connected simple graphs are
there with n vertices when n is 60. Show that the existence of a simple circuit of length k,
a) 2? b) 3? c) 4? d) 5? where k is an integer greater than 2, is an invariant for
graph isomorphism.
48. Show that each of the following graphs has no cut ver-
61. Explain howTheorem 2 can be used to determine whether
tices.
a graph is connected.
a) C n where n ≥ 3
62. Use Exercise 61 to show that the graph G 1 in Figure 2
b) W n where n ≥ 3
is connected whereas the graph G 2 in that figure is not
c) K m,n where m ≥ 2 and n ≥ 2
connected.
d) Q n where n ≥ 2
63. Show that a simple graph G is bipartite if and only if it
49. Show that each of the graphs in Exercise 48 has no cut
has no circuits with an odd number of edges.
edges.
64. In an old puzzle attributed toAlcuin ofYork (735–804), a
50. For each of these graphs, find κ(G), λ(G), and
min v∈V deg(v), and determine which of the two inequal- farmer needs to carry a wolf, a goat, and a cabbage across
ities in κ(G) ≤ λ(G) ≤ min v∈V deg(v) are strict. a river. The farmer only has a small boat, which can carry
the farmer and only one object (an animal or a vegetable).
a) a c He can cross the river repeatedly. However, if the farmer
is on the other shore, the wolf will eat the goat, and, simi-
b
larly, the goat will eat the cabbage. We can describe each
state by listing what is on each shore. For example, we can
e d use the pair (FG,WC ) for the state where the farmer and
goat are on the first shore and the wolf and cabbage are
b) b d on the other shore. [The symbol ∅ is used when nothing
a c g e is on a shore, so that (FWGC, ∅) is the initial state.]
a) Find all allowable states of the puzzle, where neither
the wolf and the goat nor the goat and the cabbage are
h f
left on the same shore without the farmer.
c) a b d) a b) Construct a graph such that each vertex of this graph
represents an allowable state and the vertices repre-
c d e f b c senting two allowable states are connected by an edge
if it is possible to move from one state to the other us-
g h i j ing one trip of the boat.
d e f
c) Explain why finding a path from the vertex represent-
k l ing (FWGC, ∅) to the vertex representing (∅, FWGC )
solves the puzzle.
51. Show that if G is a connected graph, then it is possible to
remove vertices to disconnect G if and only if G is not a d) Find two different solutions of the puzzle, each using
complete graph. seven crossings.
e) Suppose that the farmer must pay a toll of one dollar
52. Show that if G is a connected graph with n vertices then
whenever he crosses the river with an animal. Which
a) κ(G) = n − 1 if and only if G = K n .
solution of the puzzle should the farmer use to pay the
b) λ(G) = n − 1 if and only if G = K n . least total toll?