符号：给定简单无向图 $G = (V, E)$ ，分别用 $n$ 和 $m$ 表示顶点和边的个数，即 $n=|V|$ 和 $m=|E|$ 。

我们用 $A$ 表示 $G$ 的邻接矩阵，用 $\Delta$ 表示 $G$ 中三角形的个数，用 $\omega<2.376$ 表示矩阵乘法的指数，用 $(u - v - w)$ 表示一条长度为 $2$ 的简单路径（顶点依次为 $u, v, w$ ）。

$\Delta =trace(A^3)/6$ 。这个方法的复杂度为 $O(n^\omega) = O(n^{2.376})$ 。

令 $\gamma = m^{(\omega - 1)/(\omega + 1)}$ 。根据顶点的度数，将 $G$ 的顶点 $V$ 划分成两个集合：

$V_1 = \{v \in V \ \mid\ d_v \leq \gamma\}$
$V_2= \{v \in V \ \mid\ d_v > \gamma\}$

这里， $d_v$ 表示 $v$ 的度数。

我们首先枚举所有满足 $v \in V_1 的 (u - v - w)$ 。这一步可以在 $O(m \cdot \gamma)$ 内完成（对于每条边 $(u, v)$ ，如果 $v \in V_1$ ，则进一步遍历 $v$ 的邻接边）。

对于每条找到的 $(u - v - w)$ ，如果 $(u, w) \in E$ ，则 $u , v , w$ 构成三角形。这一步可算出所有包含了 $V_1$ 的点的三角形的个数。

对于任意一个在第一步中没有被统计到的三角形，它的3个顶点都属于 $V_2$ 。因此，我们首先构造 $V_2$ 的生成子图（induced subgraph），并用之前提到的基于矩阵乘法的代数方法算出剩余三角形的数量。其复杂度为 $O(|V_2|^\omega)$ 。由 $\textstyle{2m \geq \sum_{v\in V_2} d_v > |V_2|\cdot \gamma}$ ，可知 $|V_2| < 2m/\gamma$ 。

总体复杂度为:

$$O\left(m\cdot \gamma + \left(\frac{2m}{\gamma}\right)^\omega\right) = O\left(m^{2\omega/(\omega + 1)}\right) = O\left(m^{1.41}\right)$$

讨论：在稀疏图里面，我们有 $m = O(n\log n)$ ，因此第2个方法要比第1个方法有更好的渐进复杂度。

对于稠密图有 $m = \Omega(n^2)$ , 此时第1个方法更好。