1. (20 points) Let G = (V,E) be a simple undirected graph and M its adjacency matrix. Consider M2, where the matrix product is ordinary matrix multiplication. a) Show that the i, i entry [M2]ii on the...

graph theory


1. (20 points) Let G = (V,E) be a simple undirected graph and M its adjacency matrix. Consider M2, where the matrix product is ordinary matrix multiplication. a) Show that the i, i entry [M2]ii on the main diagonal of M 2 is equal to the sum of entries on row i in M . That is, [M2]ii = N∑ j=1 [M ]ij , where |V | = N . b) What does it mean? END of EXAM