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

Chapter 10, Problem 23E

(choose chapter or problem)

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.