GATE 2024 CS2 Q.17: solution and answer

Official answer: BSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. $A$ is its own inverse, so $A^2=I$.

2. For a simple undirected graph, $A$ is symmetric with zero diagonal. Then $(A^2{)}_{ij}={\sum }_k{A}_{ik}{A}_{kj}$ is the number of common neighbours of $i$ and $j$. For $i=j$ it equals $\mathrm{deg}(i)$.

3. Diagonal entries: $(A^2{)}_{ii}=\mathrm{deg}(i)=1$, so every vertex has degree exactly 1.

4. Off-diagonal entries: $(A^2{)}_{ij}=0$ for $i\ne j$. This holds automatically when every degree is 1, because two distinct vertices cannot share a neighbour (that neighbour would have degree at least 2).

5. A graph in which every vertex has degree 1 is a set of disjoint edges, that is, a perfect matching.

6. Such graphs exist. For $K_2$, $A=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$ and $A^2=I$, so (D) is false.

7. A cycle has every degree equal to 2, and $K_n$ for $n\ge 3$ has every degree equal to $n-1\ge 2$. Both violate degree 1, so (A) and (C) are not true. Only (B) always holds.