Editing Turán's theorem (section)

=== Lagrangian ===
This proof is due to {{harvtxt|Motzkin|Straus|1965}}. They begin by considering a <math>K_{r+1}</math> free graph with vertices labelled <math>1,2,\ldots,n</math>, and considering maximizing the function<math display="block">f(x_1,x_2,\ldots,x_n)=\sum_{i,j\ \text{adjacent}} x_ix_j</math>over all nonnegative <math>x_1,x_2,\ldots,x_n</math> with sum <math>1</math>. This function is known as the [[Homomorphism density#Lagrangian|Lagrangian]] of the graph and its edges.

The idea behind their proof is that if <math>x_i,x_j</math> are both nonzero while <math>i,j</math> are not adjacent in the graph, the function<math display="block">f(x_1,\ldots,x_i-t,\ldots,x_j+t,\ldots,x_n)</math>is linear in <math>t</math>. Hence, one can either replace <math>(x_i,x_j)</math> with either <math>(x_i+x_j,0)</math> or <math>(0,x_i+x_j)</math> without decreasing the value of the function. Hence, there is a point with at most <math>r</math> nonzero variables where the function is maximized.


Now, the [[Cauchy–Schwarz inequality]] gives that the maximal value is at most  <math>\frac{1}{2}\left(1-\frac{1}{r}\right)</math>. Plugging in <math>x_i=\frac{1}{n}</math> for all <math>i</math> gives that the maximal value is at least <math>\frac{|E|}{n^2}</math>, giving the desired bound.{{r|az|ms}}