proof of Turan’s theorem

If the graph $G$ has $n\le p-1$ vertices it cannot contain any $p$–clique and thus has at most $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ edges. So in this case we only have to prove that

$$\frac{n(n-1)}{2}\le \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}\le 1-\frac{1}{p-1},$$

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

Now we assume that $n\ge 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 $\left(\genfrac{}{}{0pt}{}{p-1}{2}\right)$ 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\le \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}\le (p-2)(n-p+1).$$

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

$$|E|\le \left(\genfrac{}{}{0pt}{}{p-1}{2}\right)+\frac{1}{2}\left(1-\frac{1}{p-1}\right){(n-p+1)}^2+(p-2)(n-p+1).$$

And thus we get:

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

Title	proof of Turan’s theorem
Canonical name	ProofOfTuransTheorem
Date of creation	2013-03-22 12:46:13
Last modified on	2013-03-22 12:46:13
Owner	mathwizard (128)
Last modified by	mathwizard (128)
Numerical id	6
Author	mathwizard (128)
Entry type	Proof
Classification	msc 05C99