一个有趣的定理：拉姆齐定理

noski

在组合数学上，拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。
这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。

已知的拉姆齐数非常少，保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”

R(3,3)等于6的证明
证明：在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。
任意选取一个端点P，它有5条边和其他端点相连。
根据鸽巢原理，3条边的颜色至少相同，不失一般性设这种颜色是红色。
在这3条边除了P以外的3个端点，它们互相连结的边有3条。
若这3条边中任何一条是红色，这条边的两个端点和P相连的2边便组成一个红色三角形。
若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了一个蓝色三角形。
而在K5内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点 的线是红色，和其余两个端点的连线是蓝色即可。


这个定理的通俗版本就是友谊定理。

友谊定理

友谊定理（Friendship Theorem）说明：在一群不少于三人的人中，若任何两人都刚好只有一个共同认识的人，这群人中总有一人是所有人都认识的。
在图论的角度来说，一幅图，若每个顶点都跟另一个顶点刚好只有一个共同相邻的顶点，这幅图中有一个顶点和其他顶点都相邻。

（来源Wiki）