# An upper bound for number of triangles in a graph

A small inquiry about something that has been troubling me for the whole afternoon without luck: is there any known result about say simple graphs $G(V,E)$ with some property $\mathcal{P}$ such that the number of triangles $t(G)$ is bounded above by $O(|V|^{\frac{3}{2}})$?

Sorry if it is not MO appropriate :).

-
What kind of properties are you interested in? One such property is, for example, not containing a cycle of length 5. –  Gjergji Zaimi Mar 11 '12 at 2:41

The property is that the graph be sparse, since it is easy to show that the number of triangles is $O(|E|^{3/2}),$ so as long as $E = O(V),$ your result holds. For the (simple) proof and sharp extensions see

Rivin, Igor(1-TMPL) Counting cycles and finite dimensional Lp norms. (English summary) Adv. in Appl. Math. 29 (2002), no. 4, 647–662. 05C38 (90C35)

-
Igor, many thanks, this is precisely what I was looking for. –  Cosmin Pohoata Apr 10 '12 at 4:22

A graph is $d$-degenerate if every subgraph has minimum degree at most $d$.

Claim: Every $d$-degenerate graph with $n\geq d+1$ vertices has at most $\binom{d}{2}(n-\frac{2}{3}(d+1))$ triangles.

Proof (by induction on $n$). For the base case with $n=d+1$, the number of triangles is at most $\binom{n}{3}=\binom{d}{2}(n-\frac{2}{3}(d+1))$. Let $G$ be a $d$-degenerate graph with $n\geq d+2$ vertices. There is a vertex $v$ of degree at most $d$ in $G$. The number of triangles containing $v$ is at most $\binom{d}{2}$. The number of triangles not containing $v$ (that is, in $G-v$) is at most $\binom{d}{2}(n-1-\frac{2}{3}(d+1))$ by induction (since $G-v$ is also $d$-degenerate). In total, $G$ has at most $\binom{d}{2}(n-\frac{2}{3}(d+1))$ triangles.

This upper bound is tight for every $d$-tree.

-