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 :).
 A: 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) 
A: 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. 
