Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?

Let $A$ be the $n \times n$ adjacency matrix of a simple, undirected, unweighted graph $G = (V, E)$.

• Option (A): The $(i, i)$-th entry of $A^2$ is given by:

  $$(A^2)_{ii} = \sum_{k=1}^n A_{ik} A_{ki} = \sum_{k=1}^n A_{ik}^2$$

  Since $A$ is symmetric and entries are $0$ or $1$, $A_{ik}^2 = A_{ik}$. Therefore, $(A^2)_{ii} = \sum_{k=1}^n A_{ik} = \text{deg}(v_i)$. Hence, the diagonal entries of $A^2$ are indeed the degrees of the vertices. (True)

• Option (B): For a connected bipartite graph (e.g., $K_{1,2}$ with $n=3$), $A^{n-1} + I_n = A^2 + I_3$. In $K_{1,2}$, there are no walks of length $2$ between the central vertex and a leaf vertex. Thus, non-diagonal entries connecting the two partitions in $A^2 + I_3$ remain $0$. Hence, entries in $A^{n-1} + I_n$ can be zero. (False)

• Option (C): The sum of all elements of $A$ equals $2|E|$. If $2|E| \le 2(n-1)$, then $|E| \le n-1$. A graph with $|E| \le n-1$ is not necessarily acyclic if it is disconnected (e.g., a disjoint union of a $C_3$ triangle and an isolated vertex has $n=4, |E|=3 \le 4-1$, but contains a cycle). (False)

• Option (D): Having at least a 1 in each row and column simply means that every vertex has degree $\ge 1$ (no isolated vertices). A disconnected graph such as $K_2 \cup K_2$ has at least a 1 in every row and column, but is disconnected. (False)

Therefore, only statement A is true.