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?
Answer
(B)
Explanation
\(A\) is its own inverse exactly when \(A^{2} = I\). The entry \((A^{2})_{ij}\) counts the walks of length 2 from vertex \(i\) to vertex \(j\).
- The diagonal entry \((A^{2})_{ii}\) is the degree of \(i\), so \(A^{2} = I\) forces every vertex to have degree exactly 1.
- When every degree is 1, no two vertices share a neighbour, so the off-diagonal entries are 0, as required.
So \(G\) is a set of disjoint edges, that is, a perfect matching, and every perfect matching does satisfy \(A^{2} = I\). A cycle fails because its vertices have degree 2. A complete graph works only as \(K_{2}\), a single edge, so two disjoint edges already show that C is not always true. A single edge also rules out D.
Answer: B