Combinatorics (Fall 2010)/Extremal graphs: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 2: | Line 2: | ||
=== Mantel's theorem === | === Mantel's theorem === | ||
{{Theorem|Theorem (Mantel 1907)| | |||
: If a graph <math>G</math> on <math>2n</math> vertices contains <math>n^2+1</math> edges, then <math>G</math> contains a triangle. | |||
}} | |||
== Turán's theorem == | == Turán's theorem == | ||
Revision as of 07:37, 13 October 2010
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.