Question

求证一道图论题

在几个点组成的图Gn中，若对某个2≤k≤n-2，,任意k个点间的边数相同，则Gn是完全图。
（提示上面说可以先征Gn是正则图，在证明它是完全图，请各位帮帮忙）

Answer 1

这个是图论中的Ramsey定理，题目的描述稍有问题，应该加上G是非零图的条件

1) 先证G是正则图
对于n个点，按照它们的度数从大到小排序，然后编号为v1、v2...vn，即满足d(v1)>=d(v2)>=...>=d(vn)
以下反证证明。如果G不是正则图，那就有d(v1)>d(vn)
对于V-{v1, vn}中的n-2个点，按照与v1、vn相连或者不相连，可以划分到以下4个集合中：
A：只与v1相连
B：与v1、vn都相连
C: 只与vn相连
D：与v1、vn都不相连
因为d(v1)>d(vn)，所以|A|>|C|

按照如下方法从V-{v1, vn}中挑选出k-1个点：
a) 优先从A中挑选
b) 如果从A中挑选不满，那么再从B∪D中挑选
c) 如果以上还挑选不满，最后从C中挑选
假设最后挑选出来的k-1个点落在A、B、C、D的子集分别为A'、B'、C'、D'，根据以上方法，显然有|A'|>|C'|
考察以下两个k子集：
V1={v1}∪A'∪B'∪C'∪D'
V2={vn}∪A'∪B'∪C'∪D'
e(G[V1])-e(G[V2])=|A'|-|C'|>0，这与条件任意k个点的导出子图的边数相等相矛盾
因此d(v1)=d(vn)，即G是正则图

2) 再证明对于任意的两个点，比如v1，vn，有|A|=|C|=0
1)的证明可以得到|A|=|C|
仍然通过反证证明。如果|A|=|C|>0，注意还有个条件：k-1<n-2，这说明按照刚才的挑选，C中的点必然是挑不满的，因此还是有|A'|>|C'|，导致e(G[V1])>e(G[V2])，与条件任意k个点的导出子图的边数相等相矛盾
所以|A|=|C|=0

3) 最后证G是完全图
还是通过反证证明。如果d(v1)<n-1，即存在v2，v2与v1不相连
又d(v1)=d(v2)>0，所以存在v3，使得v3与v1相连但v3不与v2相连
这样v3就落在v1、v2的A集合里面，因此|A|>0，这与2)的结论相矛盾
所以d(v1)=n-1，即G是完全图