朋友与陌路人定理

大白兔奶糖

Theorem on friends and strangers
证明：如果一群人中任意两个人总是有且仅有一个共同的朋友(朋友关系是相互的)，那么一定有一个人是所有其他人的朋友。

abababa

设有$n$个人，视为$n$个点，如果两人是朋友则在两点间连线。当$n=3$时显然成立。假设当$n=k>3$时成立，设这$k$个点为$A,B_1,B_2,\cdots,B_{k-1}$，则存在一点和其它所有点有连线，不妨设这点是$A$，由于任意两点都与某个第三点相连，因此存在$B_i\neq B_1$与$A,B_1$都相连。

当$n=k+1$时，增加一点$C$。对于$C,A$这两点，必有一点$B_i$与这两点都有连线，不妨设$B_1$与$C,A$都有连线。则$CA$之间不能连线，否则$A,B_1$这两点既与$C$都相连也与$B_i$都相连，矛盾。因此$C$不认识所有人，$A$也不认识所有人。假设$B_k,k\neq1$认识所有人，则$C,A$都和$B_k$相连，但$C,A$也和$B_1$相连，矛盾。所以只能是$B_1$认识所有人，和所有其它点都相连，由于$k>3$，因此存在线段$B_1B_2,B_1B_3$，还存在线段$AB_1,AB_2,AB_3$，于是$A,B_1$都和$B_2,B_3$相连，矛盾。因此当$k>3$时不存在一个人认识所有人。

于是只有三个人时命题成立。