一道图论题求证：在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.

Question

一道图论题
求证：在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.

Answer 1

我用反证法来证明.事实上要满足“任何两人都刚好只有一个共同认识得人”这个条件的这群人必须是奇数.
首先用一个点来代表一个人,如果A认识B,就在AB间连一条线,这样整个关系生成一个无向图G.
那么由“任何两人都刚好只有一个共同认识得人”,能得出G中没有4边形,即不存在4点A,B,C,D使得,A与B,B与C,C与D,D与A之间均有线相连.
设连线最多的点为P,与它相连的点为Q1~QK,不与它相连的点为R1~RL(L>0).
1.根据P与Q1~QK中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出Q1~QK这K个点必满足K
为偶数且这些点之间的连线情况必定是分为K/2个组,每组2个点它们之间有连线,除此之外Q1~QK间无其它连线；否则会有某对点的“共同认识得朋友”超过1个.
2.根据P与R1~RL中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出每个R1~RL中的点只与
P1~PK中的一个点有连线；否则会有某对点的“共同认识得朋友”超过1个.
3.根据Q1~QK中每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1与2的结论可以得出Q1~QK中的每个点都与R1~RL中的点有
连线；否则会有某对点的“共同认识得朋友”超过1个.
4.再取Q1~QK中按照1分组的其中两组中的每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1,2,3的结论,就能得出存在
某对点的“共同认识得朋友”超过1个的结论,矛盾!