How to show that the number of triangles in G is $\frac{1}{6}Tr(A^3)$

Question

Let's suppose we have a graph $G$. How should I show the that the number of triangle of in $G$ is $$\frac{1}{6}Tr(A^3)$$ where A is the adjacency matrix of $G$? I have no idea what should I do first. Thank you in advance

Answer 1

Let $A$ be the adjacency matrix. Then $A_{ij}=1$ iff there is an edge connecting $i\leftrightarrow j$. With this in mind, $i\rightarrow j \rightarrow k$ is a triangle iff $A_{ij}A_{jk}A_{ki}=1$. Now sum over $ijk$ and get ${\rm tr}\left(A^{3}\right)$. But wait, you over-count this by exactly the number of permutations on $ijk$, which is $3!=6$. Thus the number of triangles is

$$\text{Number of triangles}=\dfrac{1}{6}{\rm tr}\left(A^{3}\right)$$

Answer 2

The $i,j$ entry of $A^3$ gives us the number of length three walks $iklj$. If $i=j$ (and the graph has no loops), such a walk $ikli$ necessarily has $k\ne i$ and $k\ne l$, i.e., is a cycle of length $3$. As the trace is the sum of the diagonal entries, it counts such cycles - but each is counted six times, namely for each starting vertex and walking direction.