edited by
7,290 views
16 votes
16 votes

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.
edited by

4 Answers

7 votes
7 votes
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
edited by
6 votes
6 votes
edited by
2 votes
2 votes

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

Taken as such from (self explanatory)

https://www.quora.com/How-do-I-prove-this-theorem-Assume-that-A-is-the-adjacency-matrix-of-the-graph-G-Prove-that-G-is-connected-if-and-only-if-In-A-n-1-has-no-zero

“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$

Other Source : https://math.stackexchange.com/questions/2983151/prove-that-g-is-connected-if-and-only-if-the-matrix-i-n-an%E2%88%921-has-no

Answer:

Related questions

14 votes
14 votes
3 answers
1
19 votes
19 votes
5 answers
2
Arjun asked Feb 15, 2022
8,567 views
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .