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 \( 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.

Hint:

When dealing with the adjacency matrix, powers of the matrix reveal paths and walks of various lengths between vertices, and the diagonal entries of \( A^2 \) represent vertex degrees.

Answer 1

The Correct Option is A

Statement (A):
The adjacency matrix \( A \) of a graph represents the connections between vertices, where the element \( A_{ij} \) is 1 if there's an edge between vertex \( i \) and vertex \( j \), and 0 otherwise. When we square \( A \) (i.e., compute \( A^2 \)), the diagonal entries \( A_{ii} \) of \( A^2 \) represent the degree of vertex \( i \) because they count the number of walks of length 2 that start and end at vertex \( i \). Hence, Option (A) is true.

Statement (B):
The matrix power \( A^{n-1} \) represents the number of walks of length \( n-1 \) between all pairs of vertices. If the graph is connected, the powers of \( A \) allow us to reach all vertices, meaning that \( A^{n-1} \) should not contain any zero entries when added to the identity matrix \( I_n \). Thus, Option (B) is true.

Statement (C):
The sum of all elements of \( A \) gives twice the number of edges in the graph. If this sum is at most \( 2(n-1) \), then the graph is acyclic because the graph would have at most \( n-1 \) edges. This implies that the graph is a tree or a forest, hence acyclic. So, Option (C) is true.

Statement (D):
If there is at least one 1 in each row and each column of the adjacency matrix \( A \), it implies that there is at least one edge between every vertex and some other vertex, but this does not necessarily imply that the graph is connected. For example, a disconnected graph may have each row and column contain a 1, but the graph may consist of disconnected components. Thus, Option (D) is false.

Thus, the correct answers are (A), (B), and (C).
Final Answer: (A), (B), and (C)