Number of triangles in a graph based on number of edges

Question

Given a graph $G(V,E)$, what is the maximum number of triangles that this graph can have in terms of $|E|$?

I know that there is a triangle listing algorithm that lists all the triangles in $O(|E|^{3/2})$, but I need to prove that the number of triangles is actually $O(|E|^{3/2})$. Can anyone help me? Any tighter bound is also appreciated, but I need it to be based on $E$.

Answer 1

So far, I came up with a proof myself, but others may help verify this proof:

Lemma. Given a graph $G(V,E)$, the number of its triangles is $O(|E|^{1.5})$.

Proof. For each node $v$, let us denote by $A(v)$ the set $\{u \in N(v), d(u) \geq d(v)\}$; this set contains only neighbors of $v$ whose degree is no less than degree of $v$ itself.

Without loss of generality, let's consider each triangle $\Delta_{uvw}$ such that $d(u) \leq d(v) \leq d(w)$, where $d(v)$ is the degree of node $v$ in $G$. One may then discover $\Delta_{uvw}$ by checking that $w$ is in $A(u) \cap A(v)$.

Thus, we can claim that the set of triangles is $T=\{\Delta_{uvw} | (u,v) \in E, w \in A(u) \cap A(v)\}$. Therefore, we only need to prove that for every edge $(u,v) \in E$, the $|A(u)|$ and $|A(v)|$ are both $O(\sqrt{|E|})$.

Suppose $u$ has $\omega(\sqrt{|E|})$ such neighbors in $A(u)$. Since the degree of all of them is at least equal to the degree of $u$, the total number of edges become $\omega(|E|)$ which is a contradiction.

So we can claim that $|T| \in O(|E|^{1.5})$.

Answer 2

I'm pretty sure your proof can work out, but here's an alternative.

Let $t(e)$ be the maximum number of triangles in a graph with $e$ edges.

We want $t(e) \in O(e^{1.5})$.

As you may know, if $e = {k \choose 2}$ for some $k$, the graph with the most triangles is the complete graph on $k$ vertices, which has $O(e^{1.5})$ triangles. So we can say there is a $c$ such that $t(e) \leq ce^{1.5}$ whenever $e = {k \choose 2}$ for some $k$.

The problematic values of $e$ are those in-between binomial values, i.e. ${ k - 1 \choose 2} < e < {k \choose 2}$. I want to show these values of $e$ still "fit in" $O(e^{1.5})$. Let $\delta$ be such that $e + \delta = {k \choose 2}$. We can assume $\delta \leq e$. That's because $e + e > 2{k-1 \choose 2} > {k \choose 2}$ whenever $k > 4$, so a $\delta > e$ will never be required to reach the next binomial (for large enough $e$).

One last thing to note : $t$ is non-decreasing. That is, $t(e) \leq t(e + 1)$, because the maximum number of triangles we can make cannot decrease by adding an edge.

So here's what happens :

$$t(e) \leq t(e + \delta) \leq c(e + \delta)^{1.5} \leq c(2e)^{1.5} = 2^{1.5}ce^{1.5}$$

The first inequality because $t$ is non-decreasing, the second because $e + \delta = {k \choose 2}$, and the third because $\delta \leq e$ and "non-decreasingness".

So $t(e) \leq de^{1.5}$ with the constant $d = 2^{1.5}c$, and thus $t(e) \in O(e^{1.5})$.