Editing Turán's theorem (section)

=== Maximal Degree Vertex ===
This proof is due to [[Paul Erdős]]. Take the vertex <math>v</math> of largest degree. Consider the set <math>A</math> of vertices not adjacent to <math>v</math> and the set <math>B</math> of vertices adjacent to <math>v</math>.

Now, delete all edges within <math>A</math> and draw all edges between <math>A</math> and <math>B</math>. This increases the number of edges by our maximality assumption and keeps the graph <math>K_{r+1}</math>-free. Now, <math>B</math> is <math>K_r</math>-free, so the same argument can be repeated on <math>B</math>.

Repeating this argument eventually produces a graph in the same form as a [[Turán graph]], which is a collection of independent sets, with edges between each two vertices from different independent sets. A simple calculation shows that the number of edges of this graph is maximized when all independent set sizes are as close to equal as possible.{{r|az|erdos}}