in Graph Theory edited by
1,820 views
4 votes
4 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$
in Graph Theory edited by
by
1.8k views

2 Answers

10 votes
10 votes
Best answer

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
5 votes
5 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