Question

【題目】在一次數學競賽中，某些選手是朋友關系.記所有選手的集合為X，對集合X的子集Y，若可以將這些人兩兩分組，且每組中兩名選手均是朋友關系，則稱子集Y“可兩兩分組”.已知集合X不可兩兩分組，且對于任意選手，若A、B不是朋友關系，則可兩兩分組，且X中沒有一個人與其他所有人均為朋友關系證明:對任意選手，若a、b為朋友關系，b、c為朋友關系，則a、c也為朋友關系

Answer 1

【答案】見解析

【解析】

考慮一個圖G，頂點由集合X組成，若X中兩人認識，則將這兩人相連，否則不相連若一個圖中的點可以兩兩分組，且每組中兩個點均相連，則稱這種分組為圖G的一個“完美匹配”（可以看成是圖G的一個子圖）.于是，題目的條件變成了圖G不存在完美匹配，且若x、y不相連，則G＋xy（表示把這個圖G的xy也相連）存在一個完美匹配，且沒有一個點與所有點均相連.

用反證法.

若存在a、b、c使得a、b認識，b、c認識，但a、c不認識，由于沒有人認識其他所有人，故存在，使得b、d不認識.

由假設可得G＋ac有一個完美匹配，記為；G＋bd也有一個完美匹配記為.

考慮與的對稱差

.

則容易得到S是一些互不相交的圈，且每個圈均由偶數個點組成，設ac屬于圈，bd屬于圈.

分兩種情形討論

若，則在圈外的點按照的分組方式分組，在圈中按照的分組方式即可得到原圖G的一個完美匹配，即得矛盾.

若，則這個圈從b出發(fā)沿邊bd開始，不妨設首先連到點a，即b到a的路徑（首先經過邊bd）為P，于是，P＋ab為一個圈，其中，有一半的邊（間隔地）屬于對P＋ab這個圈外的點按的方式分組，而對P＋ab按ab及的方式分組即可得到原圖G的一個完美匹配，即得矛盾.