Editing Turán's theorem (section)

=== Induction ===
[[File:Turán-Induct-r=3.png|thumb|256x256px|(Induction on n) An example of sets <math>A</math> and <math>B</math> for <math>r=3</math>.]]
[[File:Turán-Erdős-Replacement.png|thumb|299x299px|(Maximal Degree Vertex) Deleting edges within <math>A</math> and drawing edges between <math>A</math> and <math>B</math>.]]
This was Turán's original proof. Take a <math>K_{r+1}</math>-free graph on <math>n</math> vertices with the maximal number of edges. Find a <math>K_r</math> (which exists by maximality), and partition the vertices into the set <math>A</math> of the <math>r</math> vertices in the <math>K_r</math> and the set <math>B</math> of the <math>n-r</math> other vertices.

Now, one can bound edges above as follows:

* There are exactly <math>\binom{r}{2}</math> edges within <math>A</math>.
* There are at most <math>(r-1)|B|=(r-1)(n-r)</math> edges between <math>A</math> and <math>B</math>, since no vertex in <math>B</math> can connect to all of <math>A</math>.
* The number of edges within <math>B</math> is at most the number of edges of <math>T(n-r,r)</math> by the inductive hypothesis.

Adding these bounds gives the result.{{r|turan|az}}