GATE CS 2024 Set 2 Q7 — Graphs: Connectivity, Matching, Colouring

We are given that $A$ is the adjacency matrix of a simple undirected graph $G$, and $A$ is its own inverse, which means:

Let us analyze the elements of the matrix $A^2$:

1. Diagonal Elements: The diagonal entry $(A^2)_{ii}$ represents the number of walks of length $2$ starting and ending at vertex $i$. For a simple undirected graph, this is equal to the degree of vertex $i$: $$(A^2)_{ii} = \text{deg}(i)$$ Since $A^2 = I$, we must have $(A^2)_{ii} = 1$ for all vertices $i$. Therefore: $$\text{deg}(i) = 1 \quad \text{for all } i$$
2. Off-Diagonal Elements: The off-diagonal entry $(A^2)_{ij}$ (where $i \neq j$) represents the number of walks of length $2$ between distinct vertices $i$ and $j$. Since $A^2 = I$, we have: $$(A^2)_{ij} = 0 \quad \text{for all } i \neq j$$ This confirms that no two distinct vertices share a common neighbor.

Since every vertex in $G$ has a degree of exactly $1$, the graph $G$ must be a 1-regular graph. A 1-regular graph consists of a set of disjoint edges covering all vertices, which is the definition of a perfect matching.

Option Elimination:

• A is incorrect: In a cycle, every vertex has a degree of $2$, so $(A^2)_{ii} = 2 \neq 1$.
• C is incorrect: In a complete graph $K_n$ (for $n > 2$), the degree of each vertex is $n-1 \neq 1$.
• D is incorrect: Any graph consisting of disjoint $K_2$ components (e.g., a single edge $K_2$) satisfies the given condition.