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

In an unweighted adjacency matrix $A$, the entry $(A^k)_{ii}$ represents the number of closed walks of length $k$ starting and ending at vertex $i$.

For $k = 3$, since the graph is simple and undirected (no self-loops and no multi-edges), every closed walk of length 3 starting at vertex $i$ corresponds to traversing a triangle (3-cycle) containing vertex $i$.

For each 3-cycle formed by vertices $\{u, v, w\}$:

• Vertex $u$ sees $2$ closed walks of length 3: $u \to v \to w \to u$ and $u \to w \to v \to u$.

• Vertex $v$ sees $2$ closed walks of length 3.

• Vertex $w$ sees $2$ closed walks of length 3.

Thus, each 3-cycle contributes $2 + 2 + 2 = 6$ to $\text{trace}(A^3) = \sum_{i} (A^3)_{ii}$.

Therefore, the number of 3-cycles is given by:

This matches option (D) ($A^3$ divided by 6).