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中心點個數的最小值為 .