Question

【题目】一个简单图中两两相邻的t个项点称为一个团，与其余每个顶点均相邻的顶点称为中心点.给定整数及满足的整数k，一个n阶简单图G中不存在k+1团，其全部k团记为.

（1）证明：；

（2）若在图G中再添加一条边就存在k+1团，求图G的中心点个数的最小值.

Answer 1

【答案】（1）见解析；（2）见解析

【解析】

将题给方程两边模3得.从而，.

记.

1.当y=1时，原方程为.

上式两边模13得.

从而，.记.

则原方程化为 ①

式①两边模5得.

从而，

则式①两边模16得，矛盾.

2.当时，原方程两边模8得.

从而，.记.

则原方程化为.

.

注意到，.

故 ②

或 ③

由方程组②得 ④

式④两边模4得.

从而，y为奇数.

则式④两边模5得，矛盾.

故方程组②无解.

由方程组③得

上式两边模4得.

从而，y为偶数.

记，则原方程化为

.

注意到，.

则.

若，由，等式两边模4得.

从而，.

记，则原方程化为.

注意到，.

则.

但此时，，矛盾.

故，，.

即.

四、1.记.

即证 ①

当m=1时，.

假设式①对成立.

对m，记，，，.

则，，.

故

②

下面证明：

因为集合C中每个点与集合A中所有点相邻，所以，组成团，但不是k+1团.

故

又

则.

于是，由式②得

故式①对正整数m也成立.

由数学归纳法，不等式得证.

2.本题条件中“差一条边就含k+1团”，属于“极图”特征.此时，有.

事实上，假设.则存在图G的某个顶点，从而，顶点v必与集合中某个顶点u不相邻.否则，构成k+1团，与极图G矛盾.现添上一条边vu，由题设条件，知图G存在k+1团，记作，则是图G的一个k团，亦矛盾.

记图G中全部中心点的集合为C.则.

再由1得.

构造等号成立的例子.令.

其中，除点与不相邻外，其他任意两点均相邻.则该图G的中心点的集合为，并且不存在k+1团（因为任取图G的k+1个顶点，总包含一点对、，但任意添加一条边 ，总能出现k+1团，G是极图.

故图G中心点个数.

综上，图G中心点个数的最小值为 .