Combinatorics (Fall 2010)/Extremal graphs

Extremal Graph Theory

Mantel's theorem

Theorem (Mantel 1907)

If a graph [math]\displaystyle{ G }[/math] on [math]\displaystyle{ 2n }[/math] vertices contains [math]\displaystyle{ n^2+1 }[/math] edges, then [math]\displaystyle{ G }[/math] contains a triangle.

Turán's theorem

Theorem (Turán 1941)

Let [math]\displaystyle{ G(V,E) }[/math] be a graph with [math]\displaystyle{ |V|=n }[/math]. If [math]\displaystyle{ G }[/math] has no [math]\displaystyle{ (k+1) }[/math]-clique, [math]\displaystyle{ k\ge 2 }[/math], then [math]\displaystyle{ |E|\le\left(1-\frac{1}{k}\right)\frac{n^2}{2} }[/math].