proof of Turan’s theorem
If the graph has vertices it cannot contain any –clique and thus has at most edges. So in this case we only have to prove that
Dividing by we get
which is true since .
Now we assume that and the set of vertices of is denoted by . If has the maximum number of edges possible without containing a –clique it contains a –clique, since otherwise we might add edges to get one. So we denote one such clique by and define .
So has edges. We are now interested in the number of edges in , which we will call , and in the number of edges connecting and , which will be called . By induction we get:
Since does not contain any –clique every vertice of is connected to at most vertices in and thus we get:
Putting this together we get for the number of edges of :
And thus we get:
|Title||proof of Turan’s theorem|
|Date of creation||2013-03-22 12:46:13|
|Last modified on||2013-03-22 12:46:13|
|Last modified by||mathwizard (128)|