Question

【題目】一個(gè)簡單圖中兩兩相鄰的t個(gè)項(xiàng)點(diǎn)稱為一個(gè)團(tuán)，與其余每個(gè)頂點(diǎn)均相鄰的頂點(diǎn)稱為中心點(diǎn).給定整數(shù)及滿足的整數(shù)k，一個(gè)n階簡單圖G中不存在k+1團(tuán)，其全部k團(tuán)記為.

（1）證明：；

（2）若在圖G中再添加一條邊就存在k+1團(tuán)，求圖G的中心點(diǎn)個(gè)數(shù)的最小值.

Answer 1

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

【解析】

將題給方程兩邊模3得.從而，.

記.

1.當(dāng)y=1時(shí)，原方程為.

上式兩邊模13得.

從而，.記.

則原方程化為 ①

式①兩邊模5得.

從而，

則式①兩邊模16得，矛盾.

2.當(dāng)時(shí)，原方程兩邊模8得.

從而，.記.

則原方程化為.

.

注意到，.

故 ②

或 ③

由方程組②得 ④

式④兩邊模4得.

從而，y為奇數(shù).

則式④兩邊模5得，矛盾.

故方程組②無解.

由方程組③得

上式兩邊模4得.

從而，y為偶數(shù).

記，則原方程化為

.

注意到，.

則.

若，由，等式兩邊模4得.

從而，.

記，則原方程化為.

注意到，.

則.

但此時(shí)，，矛盾.

故，，.

即.

四、1.記.

即證 ①

當(dāng)m=1時(shí)，.

假設(shè)式①對成立.

對m，記，，，.

則，，.

故

②

下面證明：

因?yàn)榧�合C中每個(gè)點(diǎn)與集合A中所有點(diǎn)相鄰，所以，組成團(tuán)，但不是k+1團(tuán).

故

又

則.

于是，由式②得

故式①對正整數(shù)m也成立.

由數(shù)學(xué)歸納法，不等式得證.

2.本題條件中“差一條邊就含k+1團(tuán)”，屬于“極圖”特征.此時(shí)，有.

事實(shí)上，假設(shè).則存在圖G的某個(gè)頂點(diǎn)，從而，頂點(diǎn)v必與集合中某個(gè)頂點(diǎn)u不相鄰.否則，構(gòu)成k+1團(tuán)，與極圖G矛盾.現(xiàn)添上一條邊vu，由題設(shè)條件，知圖G存在k+1團(tuán)，記作，則是圖G的一個(gè)k團(tuán)，亦矛盾.

記圖G中全部中心點(diǎn)的集合為C.則.

再由1得.

構(gòu)造等號成立的例子.令.

其中，除點(diǎn)與不相鄰?fù)猓�其他任意兩點(diǎn)均相鄰.則該圖G的中心點(diǎn)的集合為，并且不存在k+1團(tuán)（因?yàn)槿稳�圖G的k+1個(gè)頂點(diǎn)，總包含一點(diǎn)對、，但任意添加一條邊 ，總能出現(xiàn)k+1團(tuán)，G是極圖.

故圖G中心點(diǎn)個(gè)數(shù).

綜上，圖G中心點(diǎn)個(gè)數(shù)的最小值為 .