请输入您要查询的字词:

 

单词 ProofOfTuransTheorem
释义

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

n(n-1)2(1-1p-1)n22.

Dividing by n2 we get

n-1n=1-1n1-1p-1,

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:

eB12(1-1p-1)(n-p+1)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:

eA,B(p-2)(n-p+1).

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

|E|(p-12)+12(1-1p-1)(n-p+1)2+(p-2)(n-p+1).

And thus we get:

|E|(1-1p-1)n22.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 8:40:25