proof of Turan’s theorem

If the graph G has np-1 vertices it cannot contain any p–clique and thus has at most (n2) edges. So in this case we only have to prove that


Dividing by n2 we get


which is true since np-1.

Now we assume that np 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\A.

So A has (p-12) edges. We are now interested in the number of edges in B, which we will call eB, and in the number of edges connecting A and B, which will be called eA,B. By inductionMathworldPlanetmath we get:


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:


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


And thus we get:

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