定理内容

Ramsey定理的通俗表述：

6 个人中至少存在3人相互认识或者相互不认识。

该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。

注：这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。

证明

R(3,3)=6

证明如下：首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设：如果两个人认识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。

由抽屉原理可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC,CD,BD至少存在一条为红色，则至少存在三人相互认识，结论成立。若BC,CD,BD均为蓝色，则B,C,D相互不认识，结论成立。

Ramsey数

一对常数a和b，对应于一个整数r，使得r个人中或有a个人相互认识，或有b个人互不认识；或有a个人互不认识，或有b个人相互认识。这个数r的最小值用R(a,b)来表示，也就是R(a,b)个顶点的完全图。用红蓝两种颜色进行着色，无论何种情况必至少存在以下两者之一：(1)一个a个顶点着红颜色的完全子图，或一个b个顶点着蓝颜色的完全子图；(2)一个a个顶点着蓝颜色的完全子图，或一个b个顶点着红颜色的完全子图。

上述问题可以看作是R(3,3)=6的一个特例，上面的证明利用图的形象而直观的特点，证明了R(3,3)=6。

下面不用图给出R(3,3)=6的证明：

对于A以外的5个人可分为Friend和Strange两个集合。

Friend=其余5人中与A互相认识的集合；

Strange=其余5人中与A互相不认识的集合。

根据抽屉原理，Friend和Strange中有一个集合至少有3个人，不妨假设是集合Friend。

Friend中3个人P,Q,R若是彼此互相不认识，则问题已得到证明。否则有两个人互相认识，不妨设这两个人是P和Q，则A，P，Q这3个人彼此认识。

若是集合Strange至少有3个人，可以同样讨论如下：若Strange有3人L，M，N彼此互相认识，则问题的条件已得到满足。否则设L和M互不相识，则A，L，M互不相识。