a. Let G be a graphwith n vertices, and let v and w be

Problem 1E Find real numbers a, b, and c such that the following are true.

Problem 23E a. Let G be a graphwith n vertices, and let v and w be distinct vertices of G. Prove that if there is a walk from v to w, then there is a walk from v to w that has length less than or equal to n ? 1. b. If A = (ai j ) and B = (bi j ) are any m × n matrices, the matrix A + B is the m × n matrix whose i jth entry is ai j + bi j for all i = 1, 2, . . . ,m and j = 1, 2, . . . , n. Let G be a graph with n vertices where n > 1, and let A be the adjacency matrix of G. Prove that G is connected if, and only if, every entry of A + A2 +· · ·+An?1 is positive.

Problem 2E Find the adjacency matrices for the following directed graphs.

Problem 3E Find directed graphs that have the following adjacency matrices:

Problem 5E Find graphs that have the following adjacency matrices.

Problem 4E Find adjacency matrices for the following (undirected) graphs. c. K4, the complete graph on four vertices d. K2,3, the complete bipartite graph on (2, 3) vertices

Problem 6E The following are adjacency matrices for graphs. In each case determine whether the graph is connected by analyzing the matrix without drawing the graph.

Problem 9E Find each of the following products.

Problem 7E Suppose that for all positive integers i , all the entries in the ith row and ith column of the adjacency matrix of a graph are 0. What can you conclude about the graph?

Problem 10E For each of the following, determine whether the indicated product exists, and compute it if it does.

Problem 8E Find each of the following products.

Problem 11E Give an example different from that in the text to show that matrix multiplication is not commutative. That is, find 2 × 2 matrices A and B such that AB and BA both exist but AB ? BA

Problem 13E Let O denote the matrix Find 2 × 2 matrices A and B such that A ? B, B?O, and AB ? O, but BA = O.

Problem 12E Let O denote the matrix Find 2 × 2 matrices A and B such that A ? O and B ? O, but AB = O.

Problem 16E In 14–18 assume the entries of all matrices are real numbers. Prove that matrix multiplication is associative: If A, B, and C are any m × k, k × r, and r × n matrices, respectively, then (AB)C = A(BC).

Problem 14E In 14–18 assume the entries of all matrices are real numbers. Prove that if I is the m × m identity matrix and A is any am × n matrix, then IA = A.

Problem 15E In 14–18 assume the entries of all matrices are real numbers. Prove that if A is an m × m symmetric matrix, then A2 is symmetric.

Problem 18E In 14–18 assume the entries of all matrices are real numbers. Use mathematical induction to prove that if A is an m × m symmetric matrix, then for any integer n ? 1,An is also symmetric.

Problem 19E b. Let G be the graph with vertices v1, v2, and v3 and with A as its adjacency matrix. Use the answers to part (a) to find the number of walks of length 2 from v1 to v3 and the number of walks of length 3 from v1 to v3. Do not draw G to solve this problem. c. Examine the calculations you performed in answering part (a) to find five walks of length 2 from v3 to v3. Then draw G and find the walks by visual inspection.

Problem 20E The following is an adjacency matrix for a graph: Answer the following questions by examining the matrix and its powers only, not by drawing the graph: a. How many walks of length 2 are there from v2 to v3? b. How many walks of length 2 are there from v3 to v4? c. How many walks of length 3 are there from v1 to v4? d. How many walks of length 3 are there from v2 to v3?

Problem 21E Let A be the adjacent matrix for K3, the complete graph on three vertices. Use mathematical induction to prove that for each positive integer n, all the entries along the main diagonal of Anare equal to each other and all the entries that do not lie along the main diagonal are equal to each other.

Problem 22E a. Draw a graph that has as its adjacency matrix. Is this graph bipartite? (For a definition of bipartite, see exercise 37 in Section 10.1.) Note that the first row of A becomes the first column of At , the second row of A becomes the second column of At , and so forth. For instance, b. Show that a graph with n vertices is bipartite if, and only if, for some labeling of its vertices, its adjacency matrix has the form where A is a k × (n ? k) matrix for some integer k such that 0 < k < n, the top left O represents a k × k matrix all of whose entries are 0, At is the transpose of A, and the bottom right O represents an (n ? k) × (n ? k) matrix all of whose entries are 0.

Problem 17E In 14–18 assume the entries of all matrices are real numbers. Use mathematical induction and the result of exercise 16 to prove that if A is any m × m matrix, then AnA = AAn for all integers n ? 1.