Dark Mode

1,890 views

6 votes

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

- The diagonal entries of $A^{2}$ are the degrees of the vertices of the graph.
- If the graph is connected, then none of the entries of $A^{n-1} + I_{n}$ can be zero.
- If the sum of all the elements of $A$ is at most $2(n-1),$ then the graph must be acyclic.
- If there is at least a $1$ in each of $A\text{’s}$ rows and columns, then the graph must be connected.

0

3 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

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

0

@Shaik Masthan if they are using can be

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

0

0 votes

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

Taken as such from (self explanatory)

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