拉姆齐定理

在组合数学上，拉姆齐（Ramsey）定理，又称拉姆齐二染色定理，是要解决以下的问题：要找这样一个最小的数 ，使得 个人中，无论相识关系如何，必定有 个人相识或 个人互不相识。

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

拉姆齐数，用图论的语言有两种描述：

拉姆齐证明，对与给定的正整数数及，R(,)的答案是唯一和有限的。

拉姆齐数亦可推广到多于两个数：

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

显然易见的公式：R(0,)=0，R(1,)=1，R(2,)=，${\displaystyle \mathrm{R}(l_1,l_2,l_3,...,l_r)=R(l_2,l_1,l_3,...,l_r)=R(l_3,l_1,l_2,...,l_r)}$（将${\displaystyle l_i}$的顺序改变并不改变拉姆齐的数值）。

R(3,3,3)=17

更详尽的可见于

证明：在一个${\displaystyle K_6}$的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。

而在${\displaystyle K_5}$内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。