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.