GATE 2022 CS – Question 52
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) The diagonal entries of $A^2$ are the degrees of the vertices of the graph.
Explanation
- **(A) True.** $(A^2)_{ii}=\sum_ja_{ij}a_{ji}=\sum_ja_{ij}^2=\deg(i)$ (entries are 0 or 1).
- **(B) False.** In a connected bipartite graph, e.g. the path on 3 vertices, entries of $A^{n-1}+I$ can still be zero (distances of the wrong parity).
- **(C) False.** The sum of all entries of $A$ is $2|E|$. $2|E|\le2(n-1)$ means $|E|\le n-1$, which does not prevent a cycle if the graph is disconnected (e.g. a triangle plus isolated vertices).
- **(D) False.** Two disjoint edges: every row and column has a 1, but the graph is not connected.
Answer: A.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2022 CS Q58
- GATE 2021 CS (CS1) Q26
- GATE 2020 CS Q62
- GATE 2019 CS Q22
- GATE 2019 CS Q56
- GATE 2018 CS Q28
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →