Question 37

In a simple undirected graph, the $(i, i)$-th entry of $A^3$ gives the number of closed walks of length 3 starting and ending at vertex $i$.

In a simple graph (which has no self-loops and no multi-edges), any closed walk of length 3 must visit three distinct vertices $i, j, k$ forming a triangle (3-cycle).

For a specific triangle formed by vertices $\{u, v, w\}$:

• There are 2 closed walks starting at vertex $u$: $u \to v \to w \to u$ and $u \to w \to v \to u$.
• Similarly, there are 2 closed walks starting at vertex $v$, and 2 closed walks starting at vertex $w$.

Thus, each triangle contributes exactly $2 \times 3 = 6$ closed walks of length 3 to the total sum of the diagonal elements $\text{tr}(A^3) = \sum_i (A^3)_{ii}$.

Therefore, the number of triangles (3-cycles) in the graph is $\frac{\text{tr}(A^3)}{6}$.