MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 4 down vote accepted

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)

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.