Question 52

Let $A$ be the adjacency matrix of a simple undirected unweighted graph with $n$ vertices:

• (A) TRUE: The $(i, i)$-th entry of $A^2$ is:
  $$(A^2)_{ii} = \sum_{k=1}^n A_{ik} A_{ki}$$
  Since the graph is undirected, $A_{ki} = A_{ik}$. Since $A_{ik} \in \{0, 1\}$, $A_{ik}^2 = A_{ik}$. Thus:
  $$(A^2)_{ii} = \sum_{k=1}^n A_{ik} = \text{deg}(v_i)$$
  The diagonal entries of $A^2$ are precisely the degrees of the vertices.
• (B) FALSE: $(A^{n-1} + I)_{ij} = (A^{n-1})_{ij} + I_{ij}$. If the graph is bipartite, walks between vertices in the same part have even length, so $(A^{n-1})_{ij} = 0$ when $n-1$ is odd, and $I_{ij} = 0$ for $i \ne j$. Thus some off-diagonal entries can be zero even in a connected graph.
• (C) FALSE: The sum of elements of $A$ is $2|E|$. If $2|E| \le 2(n-1)$, then $|E| \le n-1$. A disconnected graph on $n$ vertices can have $|E| \le n-1$ and still contain a cycle (e.g., a triangle $C_3$ plus isolated vertices).
• (D) FALSE: Having at least one 1 in each row and column only means that every vertex has degree $\ge 1$ (no isolated vertices), but the graph can consist of two or more disjoint components (such as two disjoint triangles).

Hence, only Property (A) holds.