# proof of Turan’s theorem

If the graph $G$ has $n\leq p-1$ vertices it cannot contain any $p$–clique and thus has at most ${n\choose 2}$ edges. So in this case we only have to prove that

 $\frac{n(n-1)}{2}\leq\left(1-\frac{1}{p-1}\right)\frac{n^{2}}{2}.$

Dividing by $n^{2}$ we get

 $\frac{n-1}{n}=1-\frac{1}{n}\leq 1-\frac{1}{p-1},$

which is true since $n\leq p-1$.

Now we assume that $n\geq p$ and the set of vertices of $G$ is denoted by $V$. If $G$ has the maximum number of edges possible without containing a $p$–clique it contains a $p-1$–clique, since otherwise we might add edges to get one. So we denote one such clique by $A$ and define $B:=G\backslash A$.

So $A$ has ${p-1\choose 2}$ edges. We are now interested in the number of edges in $B$, which we will call $e_{B}$, and in the number of edges connecting $A$ and $B$, which will be called $e_{A,B}$. By induction  we get:

 $e_{B}\leq\frac{1}{2}\left(1-\frac{1}{p-1}\right)\left(n-p+1\right)^{2}.$

Since $G$ does not contain any $p$–clique every vertice of $B$ is connected to at most $p-2$ vertices in $A$ and thus we get:

 $e_{A,B}\leq(p-2)(n-p+1).$

Putting this together we get for the number of edges $|E|$ of $G$:

 $|E|\leq{p-1\choose 2}+\frac{1}{2}\left(1-\frac{1}{p-1}\right)(n-p+1)^{2}+(p-2)% (n-p+1).$

And thus we get:

 $|E|\leq\left(1-\frac{1}{p-1}\right)\frac{n^{2}}{2}.$
Title proof of Turan’s theorem ProofOfTuransTheorem 2013-03-22 12:46:13 2013-03-22 12:46:13 mathwizard (128) mathwizard (128) 6 mathwizard (128) Proof msc 05C99