The GATE Grind

GATE 2022 CS – Question 37

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

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

  1. $A^3$
  2. $A^3$ divided by 2
  3. $A^3$ divided by 3
  4. $A^3$ divided by 6

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

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →