The GATE Grind

GATE 2022 CS – Question 52

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple select

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

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

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^2)_{ii}=\sum_j a_{ij}a_{ji}=\deg(i)$, so A is true. B fails for bipartite graphs like a 3-vertex path, where parity leaves zero entries in $A^{n-1}$. C fails because a graph with at most n−1 edges can still contain a cycle. D fails for two disjoint edges.