Which of the properties hold for the adjacency matrix A of a simple undirected…

GATE · 2022 · CS · Computer Science & IT

1. A.

   The diagonal entries of $A^2$ are the degrees of the vertices of the graph.

2. B.

   If the graph is connected, then none of the entries of $A^{n-1} + I_n$ can be zero.

3. C.

   If the sum of all the elements of $A$ is at most 2($n$ – 1) then the graph must be acyclic.

4. D.

   If there is at least a 1 in each of $A’s$ rows and columns, then the graph must be connected.

Attempted by 205 students.