# Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle.

This procedure gives us the algorithmic complexity of $O(n^3)$.

It is well known that if $A$ is the adjacency matrix of $G$ then the number of triangles in $G$ is $tr(A^3)/6.$

Since matrix multiplication can be computed in time $O(n^{2.37})$ it is natural to ask:

Is there any (known) faster method for computing the number of triangles of a graph?

-

The fastest algorithm known for finding and counting triangles relies on fast matrix product and has an $\mathcal{O}(n^\omega)$ time complexity, where $\omega < 2.376$ is the fast matrix product exponent. This approach however leads to a $\theta(n^2)$ space complexity.