Number of triangles in a graph

Question

Could anybody explain to my why the asymptotic upper bound for the number of triangles in a graph with n vertices is O(n^3). I could not imagine a graph with n vertices which can contain indeed n^3 triangles.

Answer 1

Consider the complete graph $K_n$. Here, choosing any three vertices yields a triangle; and the number of ways of choosing three vertices is $$ \binom{n}{3}=\frac{n(n-1)(n-2)}{6}\sim\frac{n^3}{6}\text{ as }n\to\infty. $$ It is true that you can't ever actually have $n^3$ triangles; but, that is not what the claim says.

Instead, it says, essentially, that there is a constant $C$ and a bound $N$ so that the number of triangles in a graph on $n$ vertices is bounded by $Cn^3$ for $n\geq N$... that is, that the number of triangles is eventually bounded by a multiple of $n^3$. That's what being $O(n^3)$ means.