GATE CS 2024 Set 2 — Question 17

Let $A$ be the adjacency matrix of a simple undirected graph $G$. Since $G$ is simple, the diagonal entries of $A$ are all 0 ($A_{ii} = 0$). Since $G$ is undirected, $A$ is symmetric ($A = A^T$).Given that $A$ is its own inverse, we have $A = A^{-1}$, which implies $A^2 = I$ (the identity matrix).The diagonal entries of $A^2$ represent the degree of each vertex in the graph. Specifically:$$(A^2)_{ii} = \sum_{k} A_{ik} A_{ki} = \sum_{k} (A_{ik})^2$$Since $A_{ik} \in \{0, 1\}$, $(A_{ik})^2 = A_{ik}$. Thus, $(A^2)_{ii}$ is the sum of the entries in row $i$, which is the degree of vertex $i$.Since $A^2 = I$, we must have $(A^2)_{ii} = 1$ for all $i$. Therefore, every vertex in $G$ has a degree of exactly 1.A graph where every vertex has a degree of 1 is a collection of disjoint edges covering all vertices, which corresponds to a perfect matching.