# 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 |