Ramsey 定理

要求每一对对象都给出两种关系之一，规模足够大后，就无法让所有小群体都混杂不齐：必有一组两两同属第一种关系，或另一组两两同属第二种关系。这是对所有染色的保证，包含刻意规避单色结构的染色，不是关于随机情况的经验判断。

有限性的递归证明 ​

对 $r+s$ 归纳，设 $a=R(r-1,s)$、$b=R(r,s-1)$ 已存在。在 $K_{a+b}$ 中固定顶点 $v$，按与 $v$ 相连的边色，把其余 $a+b-1$ 个顶点分为红邻集与蓝邻集。由鸽巢原理理路鸽巢原理Pigeonhole principle · Dirichlet's box principle把多于 n 个对象放入 n 个容器时，至少一个容器包含两个对象。，红邻集至少有 $a$ 点，或蓝邻集至少有 $b$ 点，否则两者总数至多 $a+b-2$。

若红邻集有至少 $a$ 点，其内部包含红 $K_{r-1}$ 或蓝 $K_s$。前者加入 $v$ 得红 $K_r$，后者已满足结论。蓝邻集情形对称。结合单顶点基例，这既证明上界，也逐步证明所有 $R(r,s)$ 有限；并未预先假定所有 Ramsey 数已经存在。

$R(3,3)=6$ 的上界可直接复算：固定六点中的一点，它连出的五条边至少三条同色，设为红色。若这三个红邻点之间有一条红边，它与原点形成红三角形；否则三条内部边全蓝，形成蓝三角形。六人中“两两认识或两两不认识”的表述使用同样逻辑，但认识关系须按对称的二元关系建模。

下界需要另一个证据。在五个顶点上，把五边形的五条边染红，另五条对角线染蓝。红图是五圈，蓝图也构成五圈，均无三角形，所以 $R(3,3)>5$。上下界合在一起才得到精确值六；只有前一段不能证明最小性。

宿主必须覆盖每一对顶点。若只对任意稀疏图的现有边染色，任意大的路径都不含三角形，便没有同样的强制结论。多色、超图和无限版本有各自的量词与参数，不能只把本式中的数字二替换掉。

把红边看作图 $G$ 的边、蓝边看作补图的边，定理等价地说：足够大的简单图包含 $r$ 点团理路团与独立集Clique · Independent set · 团 · 独立集顶点集内部的边关系分别达到两两全有与两两全无时形成的两类结构。或 $s$ 点独立集。交换颜色又得 $R(r,s)=R(s,r)$。

递推配合二项式系数的 Pascal 恒等式可归纳得到 $R(r,s)\le (\genfrac{}{}{0ex}{}{r+s-2}{r-1})$。上界表示任何染色都失败于规避目标；下界则需要一份规避染色，或用概率方法理路概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。证明这样的染色存在。定理的有限性不意味着该上界通常精确，也不自动给出高效寻找目标团的方法。