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个的结论，矛盾！

Answer 2

你的题目是错的

Answer 3

可能看不清