GATE CS 2022 Q27 — Graphs: Connectivity, Matching, Colouring

For any adjacency matrix $A$ of a simple undirected graph, the $(i, j)$-th entry of $A^k$ represents the number of walks of length $k$ from vertex $i$ to vertex $j$.

Consequently, the diagonal entry $(A^3)_{ii}$ represents the number of closed walks of length $3$ starting and ending at vertex $i$. The trace of $A^3$ is the sum of these diagonal entries:

Consider a single $3$-cycle (triangle) containing the vertices $\{u, v, w\}$. This cycle contributes to the following closed walks of length $3$:

• Starting at $u$: $u \to v \to w \to u$ and $u \to w \to v \to u$ ($2$ walks)
• Starting at $v$: $v \to w \to u \to v$ and $v \to u \to w \to v$ ($2$ walks)
• Starting at $w$: $w \to u \to v \to w$ and $w \to v \to u \to w$ ($2$ walks)

Thus, each $3$-cycle is counted exactly $6$ times in the trace of $A^3$ (twice for each of its $3$ vertices, corresponding to the two possible directions of traversal). Therefore, the number of $3$-cycles is given by $\text{Tr}(A^3)$ divided by $6$.