Let $A$ be the adjacency matrix of a simple undirected graph $G$. Suppose $A$ is its own inverse. Which one of the following statements is always TRUE?

Let $G = (V, E)$ be a simple undirected graph with $n$ vertices and adjacency matrix $A$.

Since $G$ is simple and undirected:

• $A$ is symmetric ($A^T = A$).

• The diagonal entries are all zero ($a_{ii} = 0$).

• The entries $a_{ij} \in \{0, 1\}$.

We are given that $A$ is its own inverse, which means:

The $(i, i)$-th diagonal entry of $A^2$ is:

Since $A^2 = I$, the diagonal entries must equal $1$:

A graph where every vertex has degree $1$ is a 1-regular graph, which consists of a set of disjoint edges covering all vertices of the graph. Hence, $G$ is a perfect matching (a union of disjoint $K_2$ graphs).

Thus, (B) is always true.