GATE 2022 CS – Question 37
Consider a simple undirected unweighted graph with at least three vertices. If $A$ is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) $A^3$ divided by 6
Explanation
$(A^3)_{ii}$ counts closed walks of length 3 that start and end at vertex $i$. In a simple graph a closed walk of length 3 is exactly a triangle traversed from a chosen starting vertex in a chosen direction.
Each triangle $\{u,v,w\}$ gives $3$ starting vertices $\times$ $2$ directions $=6$ closed walks, so
$$\operatorname{tr}(A^3)=6\times(\text{number of triangles}).$$
The number of 3-cycles is $\dfrac{\operatorname{tr}(A^3)}6$: option (D).
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2022 CS Q50
- GATE 2022 CS Q52
- GATE 2022 CS Q58
- GATE 2021 CS (CS1) Q26
- GATE 2020 CS Q62
- GATE 2019 CS Q22
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →