Hello,
I've read somewhere that if A is an adjacency matrix then (1/6)*trace(A^3) equals the number of triangles in the graph. Can someone explain why?
Thanks.
The adjacency matrix is symmetric across its diagonal. So, when multiplying , consider the first column of times the first row of . Every 1 and every 0 is in the same spot. So, you get the degree of each vertex across the diagonal. What happens when the first column is multiplied with the second row? In position of , you get the number of vertices adjacent to both and . Similarly for the rest of the entries.
Now, what happens when you multiply by ? The top row of lists the number of vertices adjacent to both and for each position . Each vertex that is adjacent to both and forms a triangle. When you multiply this by the first column of , the entry of will have twice the number of triangles adjacent to . I say twice because if we have a triangle , it will be counted by both and , but since in (since is not considered adjacent to itself), the triangle will not be counted by itself. So, in , you have twice the number of triangles adjacent to . In you get twice the number of triangles adjacent to (which includes the same triangle already counted twice in . Then, that same triangle is counted another two times in . Taking the trace adds up all numbers on the diagonal. You get six times the count of triangles in the graph.