Editing Turán's theorem (section)

=== Complete Multipartite Optimization ===
This proof, as well as the Zykov Symmetrization proof, involve reducing to the case where the graph is a complete [[multipartite graph]], and showing that the number of edges is maximized when there are <math>r</math> independent sets of size as close as possible to equal. This step can be done as follows:

Let <math>S_1, S_2, \ldots, S_r</math> be the independent sets of the multipartite graph. Since two vertices have an edge between them if and only if they are not in the same independent set, the number of edges is

<math display="block">\sum_{i \neq j} \left|S_i\right|\left|S_j\right|=\frac{1}{2}\left(n^2-\sum_{i} \left|S_i\right|^2\right),</math>

where the left hand side follows from direct counting, and the right hand side follows from complementary counting. To show the <math>\left(1-\frac{1}{r}\right)\frac{n^2}{2}</math> bound, applying the [[Cauchy–Schwarz inequality]] to the <math display="inline">\sum\limits_i\left|S_i\right|^2</math> term on the right hand side suffices, since <math display="inline">\sum\limits_i\left|S_i\right|=n</math>.

To prove the Turán Graph is optimal, one can argue that no two <math>S_i</math> differ by more than one in size. In particular, supposing that we have <math>\left|S_i\right| \geq \left|S_j\right|+2</math> for some <math>i \neq j</math>, moving one vertex from <math>S_j</math> to <math>S_i</math> (and adjusting edges accordingly) would increase the value of the sum. This can be seen by examining the changes to either side of the above expression for the number of edges, or by noting that the degree of the moved vertex increases.