Complexity of counting the number of triangles of a graph
Solution 1:
Let me cite this paper from 2007 (Practical algorithms for triangle computations in very large (sparse (power-law)) graphs by Matthieu Latapy):
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.
There are some improvements for sparse graphs or if you want to list the triangles shown in the document.