有限个人，任意两个人有且只有1个公共朋友，那么一定存在1个人是所有人的朋友，这是什么数学问题? 第1页

这是友谊定理，厄多斯等三人在1966年的论文中提出。已知最简洁的证明（需要线代）来自于1999年的“Proof from THE BOOK” （https://book.douban.com/subject/1414810/，强烈推荐，本书向厄多斯先生致敬，书名的THE BOOK来自于厄多斯曾说过每个数学定理都有一个最优美的证明收录在神的数学书里）。

假设存在一个由 个顶点组成的图 ， 中每两个顶点都有且只有一个公共邻点，且没有一个顶点和所有其它顶点相邻。

1. 证明 为正则图，即所有顶点的邻点数目相同：

假设图中两点A和B不相邻。取A的任一邻点C，则BC有一个共同邻点D。对于不同的C，D也不同（不然AD有多个共同邻点）。因此可以看出B的邻点数不少于A的邻点数，反过来也可以看出A的邻点数不少于B的邻点数，得到“ 中任意两个不相邻的顶点邻点数相等”这一推论。

假设AB的唯一共同邻点为O，则ABO以外的任意点不可能和AB同时相邻，因此根据上述推论其邻点数必然等于A或B的邻点数（两者相等）。最后，根据反证假设O不和其它所有顶点相邻，必然存在一点和其不相邻，因此根据推论O的邻点数也和大家一样。设 中所有点的邻点数都等于 。

2. 证明

从任一点O出发，走一步有 个邻点，再走一步可以有 个目的地，这些目的地除非回到O本身，不然两两不同。因为任意两点必然有一个公共点，这样走两步可以到达所有的顶点。现在可以看到在这 条路径中，有 条回到O本身（如OAO，OBO等等），其它的路径目的地不同（如果存在OAC和ODC，则OC有两个共同邻点）。所以要从中扣掉 得到顶点数，即 。

3. 证明这样的图不可能存在。以下使用线代方法。

考虑图 的邻接矩阵 。可以看出 每行每列都正好有 个1，对角线均为0。则 为矩阵的特征值（ 为特征向量）。现在考虑矩阵 ，这里面位于 位置的项相当于从顶点 到 的两步路径数目，因此整个矩阵除了对角线处处为1，对角线均为 。

现在看 的特征值，其中 出现一次（对应特征向量 ）， 重复出现 次（对应特征向量）。因此的特征值中 出现一次，剩下的都是 ，假设 出现 次， 出现 次。

那么，根据特征值和等于对角线和，可得 ，可见 。转换为 ，可见 为 约数。这只有在 时才能发生。而在 时 ， 为三角形。这种情况下每个顶点都和其它两个顶点相邻，和反证假设矛盾。

因此，假设不成立，必然存在一个顶点和所有其它顶点相邻。

满足条件的图被称为友谊图，如下：