In Exercises 1-3 find the number of vertices, the number

In Exercises 1-3 find the number of vertices, the number of edges, and the degree of each vertex in the given undirected graph. Identify all isolated and pendant vertices.

In Exercises 1-3 find the number of vertices, the number of edges, and the degree of each vertex in the given undirected graph. Identify all isolated and pendant vertices.

In Exercises 1-3 find the number of vertices, the number of edges, and the degree of each vertex in the given undirected graph. Identify all isolated and pendant vertices.

Find the sum of the degrees of the vertices of each graph in Exercises 1-3 and verify that it equals twice the number of edges in the graph.

Can a simple graph exist with 15 vertices each of degree five?

Show that the sum, over the set of people at a party, of the number of people a person has shaken hands with, is even. Assume that no one shakes his or her own hand

In Exercises 7-9 determine the number of vertices and edges and find the in-degree and out-degree of each vertex for the given directed multigraph.

In Exercises 7-9 determine the number of vertices and edges and find the in-degree and out-degree of each vertex for the given directed multigraph.

In Exercises 7-9 determine the number of vertices and edges and find the in-degree and out-degree of each vertex for the given directed multigraph.

For each of the graphs in Exercises 7-9 determine the sum of the in-degrees of the vertices and the sum of the outdegrees of the vertices directly. Show that they are both equal to the number of edges in the graph.

Construct the underlying undirected graph for the graph with directed edges in Figure 2.

What does the degree of a vertex represent in the acquaintanceship graph, where vertices represent all the people in the world? What do isolated and pendant vertices in this graph represent? In one study it was estimated that the average degree ofa vertex in this graph is 1 000. What does this mean in terms of the model?

What does the degree of a vertex represent in a collaboration graph? What do isolated and pendant vertices represent?

What does the degree of a vertex in the Hollywood graph represent? What do the isolated and pendant vertices represent?

What do the in-degree and the out-degree of a vertex in a telephone call graph, as described in Example 7 of Section 9. 1, represent? What does the degree of a vertex in the undirected version of this graph represent?

What do the in-degree and the out-degree of a vertex in the Web graph, as described in Example 8 of Section 9. 1, represent?

What do the in-degree and the out-degree of a vertex in a directed graph modeling a round-robin tournament represent?

Show that in a simple graph with at least two vertices there must be two vertices that have the same degree.

Use Exercise 18 to show that in a group, there must be two people who know the same number of other people in the group.

Draw these graphs. a) \(\mathrm{K}_{7}\) b) \(\mathrm{K}_{1,8}\) c) \(K_{4.4}\) d) \(\mathrm{C}_{7}\) e) \(W_{7}\) f) \(Q_{4}\)

In Exercises 2 1-25 determine whether the graph is bipartite. You may find it useful to apply Theorem 4 and answer the question by determining whether it is possible to assign either red or blue to each vertex so that no two adjacent vertices are assigned the same color.

In Exercises 2 1-25 determine whether the graph is bipartite. You may find it useful to apply Theorem 4 and answer the question by determining whether it is possible to assign either red or blue to each vertex so that no two adjacent vertices are assigned the same color.

In Exercises 2 1-25 determine whether the graph is bipartite. You may find it useful to apply Theorem 4 and answer the question by determining whether it is possible to assign either red or blue to each vertex so that no two adjacent vertices are assigned the same color.

In Exercises 2 1-25 determine whether the graph is bipartite. You may find it useful to apply Theorem 4 and answer the question by determining whether it is possible to assign either red or blue to each vertex so that no two adjacent vertices are assigned the same color.

In Exercises 2 1-25 determine whether the graph is bipartite. You may find it useful to apply Theorem 4 and answer the question by determining whether it is possible to assign either red or blue to each vertex so that no two adjacent vertices are assigned the same color.

For which values of n are these graphs bipartite? a) Kn b) Cn c) Wn d) Qn

Suppose that a new company has five employees: Zamora, Agraharam, Smith, Chou, and Macintyre. Each employee will assume one of six responsiblities: planning, publicity, sales, marketing, development, and industry relations. Each employee is capable of doing one or more of these jobs: Zamora could do planning, sales, marketing, or industry relations; Agraharam could do planning or development; Smith could do publicity, sales, or industry relations; Chou could do planning, sales, or industry relations; and Macintyre could do planning, publicity, sales, or industry relations. a) Model the capabilities of these employees using a bipartite graph. b) Find an assignment of responsibilites such that each employee is assigned a responsibility.

Suppose that there are five young women and six young men on an island. Each woman is willing to marry some of the men on the island and each man is willing to marry any woman who is willing to marry him. Suppose that Anna is willing to marry Jason, Larry, and Matt; Barbara is willing to marry Kevin and Larry; Carol is willing to marry Jason, Nick, and Oscar; Diane is willing to marry Jason, Larry, Nick, and Oscar; and Elizabeth is willing to marry Jason and Matt. a) Model the possible marriages on the island using a bipartite graph. b) Find a matching of the young women and the young men on the island such that each young woman is matched with a young man whom she is willing to marry.

How many vertices and how many edges do these graphs have? a) Kn d) Km,n b) Cn e) Qn

Find the degree sequences for each of the graphs in Exercises 2 1-25.

Find the degree sequence of each of the following graphs. a) K4 d) K2 , 3

What is the degree sequence of the bipartite graph Kmn where m and n are positive integers? Explain your answer.

What is the degree sequence of Kn, where n is a positive integer? Explain your answer.

How many edges does a graph have if its degree sequence is 4, 3, 3, 2, 2? Draw such a graph.

How many edges does a graph have if its degree sequence is 5, 2, 2, 2, 2, I? Draw such a graph.

Determine whether each of these sequences is graphic. For those that are, draw a graph having the given degree sequence. a) 5, 4, 3, 2, 1 ,0 c) 2, 2, 2, 2, 2, 2 e) 3, 3, 2, 2, 2, 2 g) 5, 3, 3, 3, 3, 3 b) 6, 5, 4, 3, 2, 1 d) 3, 3, 3, 2, 2, 2 1) 1, 1 , 1 , 1 , 1 , 1 h) 5, 5, 4, 3, 2, 1

Determine whether each of these sequences is graphic. For those that are, draw a graph having the given degree sequence. a) 3, 3, 3, 3, 2 b) 5, 4, 3, 2, 1 c) 4, 4, 3, 2, 1 d) 4, 4, 3, 3, 3 e) 3, 2, 2, 1 , 0 1) 1, 1 , 1 , I, 1

Suppose that dl , d2, ... , dn is a graphic sequence. Show that there is a simple graph with vertices VI , V2, . , Vn such that deg( Vi) = di for i = 1, 2, ... , n and VI is adjacent to V7, . , Vd, , ,

Show that a sequence dl , d2, ... , dn of nonnegative integers in nonincreasing order is a graphic sequence if and only if the sequence obtained by reordering the terms of the sequence d2 - 1, ... , dd1 +1 - 1, dd1 +2 , "" dn so that the terms are in nonincreasing order is a graphic sequence.

Use Exercise 39 to construct a recursive algorithm for determining whether a nonincreasing sequence of positive integers is graphic.

Show that every nonincreasing sequence of nonnegative integers with an even sum of its terms is the degree sequence of a pseudograph, that is, an undirected graph where loops are allowed. [Hint: Construct such a graph by first adding as many loops as possible at each vertex. Then add additional edges connecting vertices of odd degree. Explain why this construction works.]

How many subgraphs with at least one vertex does K2 have?

How many subgraphs with at least one vertex does K 3 have?

How many subgraphs with at least one vertex does W3 have?

Draw all subgraphs of this graph. a b ~ c d

Let G be a graph with v vertices and e edges. Let M be the maximum degree of the vertices of G, and let m be the minimum degree of the vertices of G. Show that a) 2e/v :::: m. b) 2e/v ::; M.

For which values of n are these graphs regular? a) Kn b) Cn c) Wn d) Qn

For which values of m and n is Km,n regular?

How many vertices does a regular graph of degree four with 10 edges have?

In Exercises 50-52 find the union of the given pair of simple graphs. (Assume edges with the same endpoints are the same.)

In Exercises 50-52 find the union of the given pair of simple graphs. (Assume edges with the same endpoints are the same.)

In Exercises 50-52 find the union of the given pair of simple graphs. (Assume edges with the same endpoints are the same.)

The complementary graph G of a simple graph G has the same vertices as G. Two vertices are adjacent in G if and only if they are not adjacent in G. Describe each of these graphs. a) Kn b) Kmn c) en d) Qn

If G is a simple graph with 15 edges and G has 13 edges, how many vertices does G have?

If the simple graph G has v vertices and e edges, how many edges does G have?

If the degree sequence of the simple graph G is 4, 3, 3, 2, 2, what is the degree sequence of G?

If the degree sequence of the simple graph G is dl , dz, ... , dn, what is the degree sequence of G?

Show that if G is a bipartite simple graph with v vertices and e edges, then e ::s v 2 /4.

Show that if G is a simple graph with n vertices, then the union of G and G is Kn .

Describe an algorithm to decide whether a graph is bipartite based on the fact that a graph is bipartite if and only if it is possible to color its vertices two different colors so that no two vertices of the same color are adjacent.

Draw the converse of each ofthe graphs in Exercises 7-9 in Section 9. 1.

Show that (G conv )conv = G whenever G is a directed graph.

Show that the graph G is its own converse if and only if the relation associated with G (see Section 8.3) is symmetric.

Show that if a bipartite graph G = (V, E) is n-regular for some positive integer n (see the preamble to Exercise 47) and (VI , V2) is a bipartition of V, then I VI I = I Vz l. That is, show that the two sets in a bipartition of the vertex set of an n-regular graph must contain the same number of vertices.

Draw the mesh network for interconnecting nine parallel processors.

In a variant of a mesh network for interconnecting n = m 2 processors, processor P(i, j) is connected to the four processors Pi 1) mod m , j) and P(i, (j I) mod m), so that connections wrap around the edges of the mesh. Draw this variant of the mesh network for 16 processors

Show that every pair of processors in a mesh network of n = m 2 processors can communicate using O(../fi) = O(m) hops between directly connected processors.