# 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
add comment

## 1 Answer

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
add comment