Graph related problem.

Question

Show that each diagonal of $A^3$ equals twice the number of triangles passing the corresponding vertex. I cannot proceed .. can anyone give a sketch of the proof

Answer 1

Im assuming $A$ is the adjacency matrix.

One can show that the entry $(A^ n)_{ij}$ is equal to the number of walks of length $n$ from $i$ to $j$.

In the case in which $n=3$ and $i=j$ it is clear that such walks cannot repeat vertices and thus each walk gives us a triangle, but since each triangle can be trasversed in two directions we have the desired result.