GATE 2022 CS Q.52: solution and answer

GATE 2022 · CSQ.52 · 2 marks · MSQ

Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?

(A)
The diagonal entries of $A^{2}$ are the degrees of the vertices of the graph.
(B)
If the graph is connected, then none of the entries of $A^{n - 1} + I_{n}$ can be zero.
(C)
If the sum of all the elements of $A$ is at most $2 (n - 1)$ , then the graph must be acyclic.
(D)
If there is at least a 1 in each of $A$ 's rows and columns, then the graph must be connected.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Only option (A) holds: the diagonal entries of $A^{2}$ are the vertex degrees.

Official answer: ASource: Official answer key, GATE 2022 CS (IIT Kharagpur)

(A) For a simple undirected graph, $A$ is symmetric with entries $0$ or $1$ and zero diagonal. So $(A^{2})_{ii} = \sum_{j} A_{ij} A_{j i} = \sum_{j} A_{ij}^{2} = \sum_{j} A_{ij}$ , which is the number of neighbours of vertex $i$ , i.e. its degree. True.
(B) $(A^{n - 1})_{ij}$ counts walks of exactly $n - 1$ edges, not of at most $n - 1$ edges. In a bipartite graph the parity of a walk's length between two vertices is fixed by which sides they lie on.
Counterexample for (B): the path $1 - 2 - 3$ has $n = 3$ and is connected. Every walk from $1$ to $2$ has odd length, so $(A^{2})_{12} = 0$ . Also $I_{12} = 0$ , so $(A^{2} + I_{3})_{12} = 0$ . A zero entry exists, so (B) is False.
(C) The sum of all entries of $A$ is $2∣ E ∣$ , so the condition says $∣ E ∣ \leq n - 1$ . This does not force acyclicity: a triangle plus one isolated vertex has $n = 4$ and $∣ E ∣ = 3 \leq 3$ , yet it contains a cycle. False.
(D) A $1$ in every row means no vertex is isolated. It does not imply connectivity: two disjoint edges on $4$ vertices have no zero row or column, but the graph has $2$ components. False.
Only (A) holds.

KEY IDEA

$(A^{k})_{ij}$ counts walks of exactly $k$ edges. $(A^{2})_{ii}$ counts closed walks of length 2, which are the edges at $i$ , so it equals the degree. The other three statements each fail on a small graph.

WATCH OUT FOR

Reading $(A^{n - 1} + I)$ as "walks of at most $n - 1$ edges" and so concluding that connected means no zero entries. $A^{n - 1}$ only counts walks of exactly $n - 1$ edges, so parity can leave zeros (for example in a path). Another slip is treating "at most $n - 1$ edges" or "no isolated vertex" as enough for acyclic or connected.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 14 Graph theory questions, with notes

GATE 2022 CS Q.52: solution and answer

Answer and solution

More Graph theory questions