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
$tr(A^3)$ counts closed walks of length 3. Each triangle is counted 6 times (3 starting vertices × 2 directions), so the number of triangles is $tr(A^3)/6$.