GATE CS 2022 Q42 — Graphs: Connectivity, Matching, Colouring

Let us analyze each option for a simple undirected unweighted graph with $n$ vertices and adjacency matrix $A$:

1. Option A is correct: The $(i, i)$-th diagonal entry of $A^2$ is given by:$$(A^2)_{ii} = \sum_{k=1}^{n} A_{ik} A_{ki}$$Since the graph is undirected, $A$ is symmetric ($A_{ik} = A_{ki}$). Since it is unweighted, $A_{ik} \in \{0, 1\}$, which means $A_{ik}^2 = A_{ik}$. Thus:$$(A^2)_{ii} = \sum_{k=1}^{n} A_{ik}^2 = \sum_{k=1}^{n} A_{ik} = \text{deg}(v_i)$$This represents the degree of vertex $v_i$.
2. Option B is incorrect: For a path graph $P_3$ on $n=3$ vertices ($1 - 2 - 3$), the graph is connected. Here, $A^{n-1} + I_n = A^2 + I_3$. The entry $(A^2 + I_3)_{1,2} = 0$ because there is no walk of length $2$ or $0$ between vertex $1$ and vertex $2$.
3. Option C is incorrect: Let $n=4$. Consider a graph consisting of a triangle $C_3$ and one isolated vertex. The number of edges is $3$, so the sum of all elements of $A$ is $2 \times 3 = 6 \le 2(4-1) = 6$. However, the graph contains a cycle.
4. Option D is incorrect: Consider a disconnected graph consisting of two disjoint edges $K_2 \cup K_2$ ($n=4$). Every vertex has degree $1$, so every row and column of $A$ contains exactly one $1$, yet the graph is disconnected.