# Number of triangles in a graph based on number of edges

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$.

• When you say maximum, do you mean over all possible graphs on a fixed number of vertices? (In which case the complete graphs clearly achieves the maximum). – Casteels Jun 7 '14 at 5:31
• @Casteels Then $|E| = ^{|V|}C_2$. The question asks for a bound in terms of $|E|$, so clearly $|E|$ has to be fixed. Did you mean fixed number of edges with any possible number of vertices? – M. Vinay Jun 7 '14 at 5:51
• @M.Vinay Maybe, but if $|E|$ is fixed, take as few vertices as possible to force lots of triangles and the graph will be nearly complete. Also, the complete graph has ${|V| \choose 3}$ triangles, which is $O(|E|^{3/2})$, no? – Casteels Jun 7 '14 at 6:12
• The question is : given that you graph has $|E|$ edges, how many triangles are there in the worst case, with respect to $|E|$ only. It's harder than it sounds, really. Yes a complete graph has $O(|E|^{3/2})$ triangles, but is that the worst case ? Is there a worse setup such that you get, say, $\Theta(|E|^{3/2 + 0.1})$ triangles ? The difficulty is that $|V|$ is irrelevant here. – Manuel Lafond Jun 7 '14 at 6:15
• @Casteels Yes, so you meant fixed number of edges, not fixed number of vertices. – M. Vinay Jun 7 '14 at 6:16

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})$.

• That's a nice way ! I think that makes sense, though to be fully convinced you'd need to show formally that $T$ misses no triangle. The last statement would also require some more detail IMO. For instance, say $u$ has $|E|^{0.51}$ neighbors in $A(u)$. Then you could say that each $v \in A(u)$ has $|E|^{0.51} - 1$ edges not incident to $u$, and that we get a total of $|E|^{0.51}(|E|^{0.51} - 1)$ edges (note that we double-count edges within $A(u)$). This is smaller than $|E|$ if $|E| = 10$ for instance. So I think you need to show there is a certain $|E|$ from which it starts working. – Manuel Lafond Jun 7 '14 at 20:15
• @manuellafond I need to prove that $T$ doesn't miss any triangle; About the reasoning, if we approach this prove that way: For $u$ we have $|E|^{0.5}$ neighbors in $A(u)$, and for every $v \in A(u)$ we have $(|E|^{0.5}-1)$ candidates to form the triangles. Thus it should be $|V|.(|E| - |E|^{0.5})$. But we know that $|E|^{3/2}$ is a tighter bound than $|V|.|E|$. – orezvani Jun 9 '14 at 7:33

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})$.