Determine whether the given graph is connected.

Determine whether the given graph is connected.

What do the connected components of acquaintanceship graphs represent?

Explain why in the collaboration graph of mathematicians (see Example 3 in Section 10.1) a vertex representing a mathematician is in the same connected component as the vertex representing Paul Erdös if and only if that mathematician has a finite Erdös number.

In the Hollywood graph (see Example 3 in Section 10.1), when is the vertex representing an actor in the same connected component as the vertex representing Kevin Bacon?

Determine whether each of these graphs is strongly connected and if not, whether it is weakly connected.

Find the strongly connected components of each of these graphs.

Find the strongly connected components of each of these graphs.

Show that if G=(V,E) is a directed graph and u,v,and w are vertices in V for which u and v are mutually reachable and v and w are mutually reachable, then u and w are mutually reachable.

Show that if G = (V , E) is a directed graph, then the strong components of two vertices u and v of V are either the same or disjoint. [Hint: Use Exercise 10.]

Find the number of paths of length n between two different vertices in K_4 if n is
a) 2.
b) 3.
c) 4.
d) 5.

Use paths either to show that these graphs are not isomorphic or to find an isomorphism between them.

Find the number of paths of length n between any two adjacent vertices in K_(3,3) for the values of n in Exercise 12.

Find the number of paths of length n between any two nonadjacent vertices in K_(3,3) for the values of n in Exercise 12.

Find the number of paths between c and d in the graph in Figure 1 of length
a) 2.
b) 3.
c) 4.
d) 5.
e) 6.
f) 7.

Find the number of paths from a to c in the directed graph in Exercise 7(b) of length
a)2.
b)3.
c)4.
d)5.
e)6.
f)7.

Show that every connected graph with n vertices has at least n − 1 edges.

Let G = (V,E) be a simple graph. Let R be the relation on V consisting of pairs of vertices (u, v) such that there is a path from u to v or such that u = v. Show that R is an equivalence relation.

Show that in every simple graph there is a path from every vertex of odd degree to some other vertex of odd degree.

Find all the cut vertices of the given graph.

Find all the cut vertices of the given graph.

Find all the cut vertices of the given graph.

Find all the cut edges in the graphs in Exercises 21–23.

A communications link in a network should be provided with a backup link if its failure makes it impossible for some message to be sent. For each of the communications networks shown here in (a) and (b), determine those links that should be backed up.

Find a vertex basis for each of the directed graphs in Exercises 5–6 of Section 10.2.

What is the significance of a vertex basis in an influence graph (described in Example 2 of Section 10.1)? Find a vertex basis in the influence graph in that example.

Show that if a connected simple graph G is the union of the graphs G1 and G2, then G1 and G2 have at least one common vertex.

Show that if a simple graph G has k connected components and these components have n1,n2,...,nk vertices, respectively, then the number of edges of G does not exceed
C(n1,2)+C(n2,2)+...+C(nk,2).

Use Exercise 29 to show that a simple graph with n vertices and k connected components has at most (n − k)(n − k + 1)/2 edges. [Hint: First show that
(n1)^2+(n2)^2+...+(nk)^2<=n^2-(k-1)(2n-k),
where ni is the number of vertices in the ith connected component.]

Show that a simple graph G with n vertices is connected if it has more than (n − 1)(n − 2)/2 edges.

Describe the adjacency matrix of a graph with n connected components when the vertices of the graph are listed so that vertices in each connected component are listed successively.

How many nonisomorphic connected simple graphs are there with n vertices when n is
a) 2?
b) 3?
c) 4?
d) 5?

Show that each of the following graphs has no cut vertices.
a) C_n where n≥3
b) W_n wheren≥3
c) K_(m,n) where m≥2 and n≥2
d) Q_n where n≥2

Show that each of the graphs in Exercise 34 has no cut edges.

For each of these graphs, find κ(G), λ(G), and min_(v∈V) deg(v), and determine which of the two inequalities in κ(G) ≤ λ(G) ≤ min_(v∈V) deg(v) are strict.

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 complete graph.

Show that if G is a connected graph with n vertices then
a) κ(G)=n−1 if and only if G=K_(n).
b) λ(G)=n−1 if and only if G=K_(n).

Find κ(K_(m,n)) and λ(K_(m,n)), where m and n are positive integers.

Construct a graph G with κ(G) = 1, λ(G) = 2, and min_(v∈V) deg(v) = 3.

Show that if G is a graph, then κ(G) ≤ λ(G).

Explain how Theorem 2 can be used to find the length of the shortest path from a vertex v to a vertex w in a graph.

Use Theorem 2 to find the length of the shortest path between a and f in the graph in Figure 1.

Use Theorem 2 to find the length of the shortest path from a to c in the directed graph in Exercise 7(b).

Let P1 and P2 be two simple paths between the vertices u 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.

Show that the existence of a simple circuit of length k, where k is an integer greater than 2, is an invariant for graph isomorphism.

Explain how Theorem 2 can be used to determine whether a graph is connected.

Use Exercise 47 to show that the graph G1 in Figure 2 is connected whereas the graph G2 in that figure is not connected.

Show that a simple graph G is bipartite if and only if it has no circuits with an odd number of edges.

In an old puzzle attributed to Alcuin of York (735–804), a farmer needs to carry a wolf, a goat, and a cabbage across a river. The farmer only has a small boat, which can carry the farmer and only one object (an animal or a vegetable). He can cross the river repeatedly. However, if the farmer is on the other shore, the wolf will eat the goat, and, simi- larly, the goat will eat the cabbage. We can describe each state by listing what is on each shore. For example, we can use the pair (FG,WC ) for the state where the farmer and goat are on the first shore and the wolf and cabbage are on the other shore. [The symbol ∅ is used when nothing 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 left on the same shore without the farmer.

b) Construct a graph such that each vertex of this graph represents an allowable state and the vertices representing two allowable states are connected by an edge if it is possible to move from one state to the other using one trip of the boat.

c) Explain why finding a path from the vertex representing (FWGC, ∅) to the vertex representing (∅, FWGC ) solves the puzzle.
d) Find two different solutions of the puzzle,eachusing seven crossings.
e) Suppose that the farmer must pay a toll of one dollar whenever he crosses the river with an animal. Which solution of the puzzle should the farmer use to pay the least total toll?

Use a graph model and a path in your graph, as in Exercise 50, to solve the jealous husbands problem. Two married couples, each a husband and a wife, want to cross a river. They can only use a boat that can carry one or two people from one shore to the other shore. Each husband is extremely jealous and is not willing to leave his wife with the other husband, either in the boat or on shore. How can these four people reach the opposite shore?