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?
 A: 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.
A: In Competitive Programming, we have a particularly popular algorithm for a rather sparse graph running in $O(m\sqrt{m})$ time complexity where $m$ is the number of the edges in the graph. Although it is certainly not the fastest, as Listing mentioned, it's still efficient in most cases.
Let $G$ denote the original graph.
The algo goes in this way:

*

*add directions to the edges in the original undirected graph according to the degree of the vertices in the original graph $G$, say the original edge $(u,v)$ is now $(u\rightarrow v)$ iff $d(u)<d(v)$ where $d(\cdot)$ denotes the degree of a vertex in $G$. In this way we get a new directed graph $G^\prime$. The triangle in $G$ transformed to this triple-edge-tuple: $((u\rightarrow v), (u\rightarrow w), (v\rightarrow w))$.


*Firstly enumerate each vertex $u$, and then enumerate all its out-neighbours in the descending order of degree, i.e. we enumerate the neighbour $v_2$ ahead of the neightbour $v_1$ if $d(v_2) > d(v_1)$. And when enumerating, we mark the neighbour with the unique timestamp of $u$ so that we can know whether we have gone through a vertex before. NOTE that here out-neighbour means the neighbour in the directed graph $G^\prime$ instead of original graph $G$, i.e. $v$ is the out-neightbour of $u$ iff there is an edge $(u\rightarrow v)$ in $G^\prime$.


*Now we already have two vertices $u$ and $v$ and then we enumerate the out-neighbour of $v$ denoted as $w$, and we can easily check if there is an edge $(u\rightarrow w)$ because of the timestamp we made in step 2. The number of $w$ that there is an edge $(u\rightarrow w)$ is the number of the triangles that $u$ and $v$ can form.
In this way, we can obviously count all the triangles. And here is the proof of time complexity.
The key principle is to illustrate the degree in new graph $G^\prime$ is rather small. Consider an arbitrary vertex $u$, if its degree in original graph is $d(u)\le\sqrt{m}$, then its out-degree $d_{+}^\prime(u)$ in new graph $G^\prime$ is certainly also less than or equal to $\sqrt{m}$. If $d(u)>\sqrt{m}$, then $d_{+}^\prime(u)$ will not be greater than $2\sqrt{m}$ because the directed edge in new graph is from a smaller-degree vertex to a larger-degree vertex, and there won't be more than $2\sqrt{m}$ vertices with degree larger than $\sqrt{m}$.
This is a pretty algorithm, hope it could inspire the following readers here.
