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.