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出发沿边bd开始，不妨设首先连到点a，即b到a的路径（首先经过边bd）为P，于是，P＋ab为一个圈，其中，有一半的边（间隔地）属于对P＋ab这个圈外的点按的方式分组，而对P＋ab按ab及的方式分组即可得到原图G的一个完美匹配，即得矛盾.