3,194 views

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\text{’s}$ rows and columns, then the graph must be connected.

@Deepak Poonia Sir, in exam I did it by option elimination, exactly like the above link. But it cost me 3 qs time :( Can you give your answer on this q?

@Abhrajyoti00

This question is indeed time taking during those 3 hours of GATE exam. But during the preparation phase, Complete Analysis of every question is More Important than just somehow getting the answer.

Most students move on after getting the answer somehow, by option elimination etc.. which is a BAD thing to do during preparation.

You can find Complete Analysis of this question below:

This GATE 2022 Question Complete Analysis

Understand Powers of Adjacency Matrix of a Graph

Applications of Powers of Adjacency Matrix of a Graph

Simple undirected Adjacency matrix representation of  Simple undirected unweighted graph

A should have diagonal entries as 0 ( because no self loops allowed in simple graphs )

A should be Symmetric matrix

Option A :

A$^2$ diagonal elements = (1.1 or 0.0) + (1.1 or 0.0) + ….. + (1.1 or 0.0)  [ n times ]

let some specific node C, if C - A edge present , then 1.1 instead of 0.0 with respect to node A in above eqn

therefore for each edge between C and Veertex$_x$, thereshould be one 1 in the above eqn

Therefore A$^2$ diagonal elements = degree of the vertices of the graph

Option B :

Counter example :  U --- V ---- W

Option C :

If there are isolated vertices and even though cycle present, then there is a possibility of sum of all elements of A is atmost 2(n-1).

So given statement is wrong.

Option D :

If there are 2 components with each component have more than one vertex, then also atleast one entry of each row and column is non-zero.

So given statement is wrong.

only Option A is true

Sir in "can be" The statement is true for some graphs.....

But for the statement to be always true they will use "must be"

@Shaik Masthan  if they are using can be

it means that there is a possibility of a graph in which the statement is true

The matrix A
n-1 + In represents number paths upto length n-1
between pair of vertices, for a connected graph there will be at least one path
between each pair of vertices , thus all entries of A
n-1 + In will be non zero.

Option (B) is actually a Theorem given incorrectly. The correct statement of the Theorem is

Taken as such from (self explanatory)

### “A Graph G is connected if and only if the matrix $\left ( I_{n}+A \right )^{n-1}$has no 0's.”

Let $G$ be a graph with vertices $v_1,\ldots,v_n$, and let $A$ be the adjacency matrix of $G$. Recall that

$\big(A\big)_{ij} = a_{ij} = \begin{cases} 0 & \text{ if}\:\:v_i \not\leftrightarrow v_j, \\ 1 & \text{ if}\:\:v_i \leftrightarrow v_j. \end{cases}$

Recall that $G$ is said to be connected if there is a $u-v$ path for every pair of distinct vertices $u$, $v$.

A $u-v$ walk is a finite and alternate sequence of vertices and edges starting with vertex $u$ and ending with vertex $v$, with each edge joining the vertices immediately preceding and immediately succeeding it:

$u\,e_1\,w_1\,e_2\,w_2\,\ldots \,w_{k-1}\,e_k\,w_k=v$,

with $e_1$ joining $u$ with $w_1$, $e_2$ joining $w_1$ with $w_2$, and so on, and $e_k$ joining $w_{k-1}$ with $v$.

A $u-v$ path is a $u-v$ walk in which all vertices are distinct.

Proposition 1: Every $u-v$ walk contains a $u-v$ path.

Proof: Consider any $u-v$ walk. If the vertices in this walk are distinct, the walk is a path. Otherwise, let $w$ be the first vertex in the walk that appears again in the walk. Consider the walk with the portion joining the two occurrences of $w$ deleted from the original walk. The shorter walk has one occurrence less of a repeated vertex. Carrying out the shortening of walks with repeated vertices results in $u-v$ walks, ultimately with distinct vertices. We have arrived at a $u-v$ path once this is achieved. $\blacksquare$

For $k \in \mathbb N$ and $i,j \in \{1,\ldots,n\}$, let $a_{ij}^{(k)}$ denote the $ij^{\text{th}}$ entry in the matrix $A^k$. Thus, $a_{ij}^{(1)}=a_{ij}$.

Proposition 2: $k \in \mathbb N$and $i,j \in \{1,\ldots,n\}$, $a_{ij}^{(k)}$ equals the number of $v_i-v_j$ walks of length $k$.

Proof: A $v_i-v_j$ walk is of length $1$ is the same as saying $v_i \leftrightarrow v_j$. Thus the result holds for $k=1$. Assume the result holds for all positive integers $<k$.

Every $v_i-v_j$ walk of length $k$ starts with an edge $v_i-v_r$ followed by a $v_r-v_j$ walk of length $k-1$. To enumerate all $v_i-v_j$ walks of length $k$, we must therefore add the number of $v_r-v_j$ walks of length $k-1$ provided $v_r \leftrightarrow v_i$. Since $a_{ir}=0 \Leftrightarrow i \not\leftrightarrow v_r$ and $a_{ir}=1 \Leftrightarrow i \leftrightarrow v_r$, the number of $v_i-v_j$ walks of length $k$ is

$\displaystyle \sum_{r=1}^n a_{ir} \cdot a_{rj}^{(k-1)} = a_{ij}^{(k)}.$

The last identity is got by taking the $ij^{\text{th}}$ entry in both sides of the matrix identity $A^k=A \cdot A^{k-1}$.

This completes the proof by mathematical induction. $\blacksquare$

Theorem: $G$ is connected if and only if $\big(I_n+A\big)^{n-1}$ has no zero entry, where $I_n$ is the $n \times n$ identity matrix.

Proof: The $ij^{\text{th}}$ of the matrix

\begin{align} \big(I_n+A\big)^{n-1} & = I_n + \binom{n-1}{1}\,A + \cdots + \binom{n-1}{n-2}\,A^{n-2} + A^{n-1} \\ & = \displaystyle \sum_{k=0}^{n-1} \binom{n-1}{k}\,A^k \end{align}

is $\displaystyle \sum_{k=0}^{n-1} \binom{n-1}{k}\,a_{ij}^{(k)}$.

This equals $0$ if and only if $a_{ij}^{(k)}$ for each $k \in \{0,1,2,\ldots,n-1\}$, or in other words, precisely when there is no $v_i-v_j$ walk of length $<n$. However, $G$ is connected if and only if there is a $v_i-v_j$ path $($hence, also a $v_i-v_j$ walk$)$ for each pair $i$, $j$, $i \ne j$. $\blacksquare$

A, B

In graph is connected then none of entries is zero in A^n-1 + In