retagged by
7,356 views
14 votes
14 votes

Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of

  1. $\textit{A}^{3}$
  2. $\textit{A}^{3}$ divided by $2$
  3. $\textit{A}^{3}$ divided by $3$
  4. $\textit{A}^{3}$ divided by $6$
retagged by

3 Answers

Best answer
30 votes
30 votes

Answer : D

$\color{red}{\text{Method 1 (How to solve instantly in Exam) :   }}$ 
Take a cycle graph on 3 vertices i.e. $C_3$.
Write the adjacency matrix $A$ of $C_3$, find $A^3$. The trace of $A^3$ is 6, but we only have one 3-cycle(3 length cycle) in $C_3$, So, we have to divide the trace of $A^3$ by 6 to find out the number of 3-cycles. That’s our answer. Option D.


$\color{blue}{\text{Method 2 (Complete Analysis) :   }}$ 
Definition of Walk : A walk consists of an alternating sequence of vertices and edges consecutive elements of which are incident, that begins and ends with a vertex. 
In simple words, Walk from vertex $w$ to $v$ is sequence of “adjacent edges”, starting from $w,$ ending at $v,$ possibly with repetition of vertices or edges or both. Length of a walk is the number of edges on it.

For example, if we have cycle graph $C_3$ whose vertices are $P,Q,R,$  then, we have 2 walks of length 3 from $P$ to $P$ $(P \rightarrow Q \rightarrow R \rightarrow P ; P \rightarrow R \rightarrow Q \rightarrow P),$ similarly 2 walks of length 3 from $R$ to $R$ ; one walk of length 1 from $P$ to $R$ etc.

The Adjacency Matrix of a Graph :
The adjacency matrix $M$ of a undirected graph is a matrix, by numbering the vertices, say from $1$ up to $n$, and then putting $M_{ij} = M_{ji} = 1 $ if there is an edge between $i$ and $j$, and $M_{ij} = 0$ otherwise.

We can do the same for a digraph: putting $M_{ij} = 1$ if there is an edge from $i$ to $j$, and $M_{ij} = 0$ otherwise.

Refer here to understand Adjacency Matrix of a Graph :
https://en.wikipedia.org/wiki/Adjacency_matrix
http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section1-1.pdf

$\color{blue}{\text{Powers of the Adjacency Matrix :  }}$ 

Let $G$ be a graph (directed or undirected simple graph), $n \in \mathbb{N}$, Let $M$ be the adjacency matrix of $G.$

The powers of the adjacency matrix count things. In particular,


$\color{blue}{Entry \,\, i, j \,\, in \,\, M^n\, \text{ gives the number of walks from } i\,\, to\,\, j\,\, of\,\, length\,\, n.}$ 


The proof is by induction argument. For example, the number of walks of length 2 from $i$ to $j$ is the number of vertices $k$ such that there is an edge from $i$ to $k$ and an edge from $k$ to $j$. And this is exactly the $i, j$ entry in $M^2$ , by the definition of matrix multiplication.


Also, NOTE that for any graph $G$ (directed or undirected simple graph), we can see that, every entry in adjacency matrix basically tells us that Number of walks of length $1$ between the corresponding vertices of that entry, So, if $M_{ij} $ is 1, it means there is walk of length $1$ from $i$ to $j,$ which is basically edge from $i$ to $j.$

So, we have the following very Important Theorem :

If $A$ is the adjacency matrix of a directed or undirected simple graph $G$, then the matrix $A^n$ (i.e., the matrix product of n copies of $A$) has an interesting interpretation:

The element $(i,j)$ gives the number of (directed or undirected) walks of length $n$ from vertex $i$ to vertex $j$.


Result : $\color{blue}{\text{The number of triangles in an undirected simple graph is exactly the trace of } A^3 \text{divided by 6.} }$  Why ??

Proof :

Note that in any simple undirected graph, we get a walk of length 3 from a vertex $X$ to the same vertex $X$ if and only if there is a triangle which contains $X$.
In any simple undirected graph, If you have a triangle $T$ between vertices $P,Q,R,$ then because of this particular triangle $T$, we have two walks of length 3 from $P$ to $P$ ; two walks of length 3 from $Q$ to $Q$ ; two walks of length 3 from $R$ to $R$ ;  So, because of this one triangle $T$, in $A^3,$ we have contribution of 2 in entry $(P,P)$ ; contribution of 2 in entry $(Q,Q)$ ; contribution of 2 in entry $(R,R)$ ; Hence, in the trace of $A^3,$ due to one triangle we have contribution of 6. So, the number of triangles in an undirected graph $G$ is exactly the trace of $A^3$ divided by 6.

For example, take a cycle graph on 3 vertices i.e. $C_3$.
Write the adjacency matrix $A$ of $C_3$, find $A^3$. The trace of $A^3$ is 6, but we only have one 3-cycle in $C_3$, So, we divide the trace of $A^3$ by 6 to find out the number of 3-cycles.

$\color{blue}{\text{Variation :  }}$
What happens if you have Simple Directed Graph ??

In any simple directed graph, If you have a directed triangle $T$ between  vertices $P,Q,R,$ $(P \rightarrow Q \rightarrow R \rightarrow P),$ then because of this particular triangle $T$, we have one walk of length 3 from $P$ to $P$ ; one walk of length 3 from $Q$ to $Q$ ; one walk of length 3 from $R$ to $R$ ;  So, because of this one triangle $T,$ in $A^3,$ we have contribution of 1 in entry $(P,P)$ ; contribution of 1 in entry $(Q,Q)$ ; contribution of 1 in entry $(R,R)$ ; Hence, in the trace of $A^3,$ due to one triangle we have contribution of 3. So, the number of triangles in an simple directed graph $G$ is exactly the trace of $A^3$ divided by 3.

For example, take a directed cycle graph on 3 vertices $P,Q,R,$ i.e. $(P \rightarrow Q \rightarrow R \rightarrow P),$.
Write the adjacency matrix $M$ of this graph, find $M^3$, the trace of $M^3$ is 3, but we only have one 3-cycle in this graph, So, we divide the trace of $M^3$ by 3 to find out the number of 3-cycles in simple directed graph.


Find my answer on a Similar question here : GATE CSE 2021 Set 1 | Question: 36
https://gateoverflow.in/357415/Gate-cse-2021-set-1-question-36

My explanation on the GATE 2021 Question in the above link has ALL the concepts needed to solve this GATE 2022 question.
 

selected by
19 votes
19 votes

Let the graph be 

corresponding adjacency matrix is A.

A=$\begin{bmatrix} 0 &1 &1 \\ 1 &0 &1 \\ 1 & 1 & 0 \end{bmatrix}$

Now A^2=A.A

               =$\begin{bmatrix} 0 &1 &1 \\ 1 &0 &1 \\ 1 & 1 & 0 \end{bmatrix}$$\begin{bmatrix} 0 &1 &1 \\ 1 &0 &1 \\ 1 & 1 & 0 \end{bmatrix}$

              =$\begin{bmatrix} 2 &1 &1 \\ 1 &2 &1 \\ 1 & 1 & 2 \end{bmatrix}$

A^3=A^2.A=$\begin{bmatrix} 2 &1 &1 \\ 1 &2 &1 \\ 1 & 1 & 2 \end{bmatrix}$$\begin{bmatrix} 0 &1 &1 \\ 1 &0 &1 \\ 1 & 1 & 0 \end{bmatrix}$

A^3=$\begin{bmatrix} 2 &3 &3 \\ 3 &2 &3 \\ 3 & 3 & 2 \end{bmatrix}$

Now Trace of A^3=2+2+2=6

no of 3-cycle in our graph is 1.

so only option D satisfies our answer.

So D is the answer.

 

 

edited by
Answer:

Related questions

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