GATE CSE 2022 Q52

Question

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
A) The diagonal entries of A2 are the degrees of the vertices of the graph.
B) If the graph is connected, then none of the entries of An-1 + In 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.

Accepted Answer

Official answer: A) The diagonal entries of A2 are the degrees of the vertices of the graph.. Explanation: Let A be the n n adjacency matrix of a simple, undirected, unweighted graph G = (V, E). - Option (A): The (i, i)-th entry of A2 is given by: (A2)ii = k=1n Aik Aki = k=1n Aik2 Since A is symmetric and entries are 0 or 1, Aik2 = Aik. Therefore, (A2)ii = k=1n Aik = deg(vi). Hence, the diagonal entries of A2 are indeed the degrees of the vertices. (True) - Option (B): For a connected bipartite graph (e.g., K1,2 with n=3), An-1 + In = A2 + I3. In K1,2, there are no walks of length 2 between the central vertex and a leaf vertex. Thus, non-diagonal entries connecting the two partitions in A2 + I3 remain 0. Hence, entries in An-1 + In can be zero. (False) - Option (C): The sum of all elements of A equals 2|E|. If 2|E| 2(n-1), then |E| n-1. A graph with |E| n-1 is not necessarily acyclic if it is disconnected (e.g., a disjoint union of a C3 triangle and an isolated vertex has n=4, |E|=3 4-1, but contains a cycle). (False) - Option (D): Having at least a 1 in each row and column simply means that every vertex has degree 1 (no isolated vertices). A disconnected graph such as K2 K2 has at least a 1 in every row and column, but is disconnected. (False) Therefore, only statement A is true.

Answer

A) The diagonal entries of A2 are the degrees of the vertices of the graph.

Answer

B) If the graph is connected, then none of the entries of An-1 + In can be zero.

Answer

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

Answer

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

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

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2022

More on Graph Theory

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

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2022

More on Graph Theory

Which of the properties hold for the adjacency matrix AAA of a simple undirected unweighted graph having nnn vertices?

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2022

More on Graph Theory

Share this solution

Which of the properties hold for the adjacency matrix AAA of a simple undirected unweighted graph having nnn vertices?

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2022

More on Graph Theory

Share this solution

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

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