Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices? A. The diagonal entries of A^2 are the degrees of the vertices of the graph. B. If the graph is connected, then none of the entries of A^(m-1) can be zero. C. If the sum of all the elements of A^m is at most n+10 for some m, then the graph must be acyclic. D. If there is at least a 1 in each of A's rows and columns, then the graph must be connected.

GATE 2022 · Discrete Mathematics · Graph Connectivity · medium

Answer: Only option A is always true: the diagonal entries of A^2 equal the degrees of the vertices.

1. Verify option A: (A^2)_{ii} = deg(i): (A^2)_{ii} = sum_k A[i][k] * A[k][i] = sum_k A[i][k]^2 = sum_k A[i][k] = deg(i), since A[i][k] in {0,1} so A[i][k]^2 = A[i][k].
2. Eliminate options B, C, D via counterexamples: B: The path P_4 is connected but (A^2)_{1,4}=0, showing A^(n-1) can have zeros. C: A cycle of length 4 has sum of entries in A^m bounded but is cyclic. D: Two disjoint edges give each vertex degree 1 (so each row/column has a 1) but the graph is disconnected.