形式陈述

对正整数 $r,s$，存在最小整数 $R(r,s)$，使任意对 $K_{R(r,s)}$ 的边作红蓝染色，都含红色 $K_r$ 或蓝色 $K_s$。递推

$$R(r,s)\le R(r-1,s)+R(r,s-1)$$

通过考察一个顶点的两种颜色邻集证明所有 Ramsey 数有限。

直觉

规模足够大时，即使染色完全任意，也无法永远避免某种较大的单色秩序。

例子与边界

经典结论是 $R(3,3)=6$。定理主要保证存在性，通常不给紧确阈值；多色、超图与无限版本需要另行表述。

推论与应用

它奠定 Ramsey 理论，并连接概率方法、逻辑紧致性和极值组合。

参考资料

• Reinhard Diestel, Graph Theory, 6th ed. (2025), Ramsey theory.
• Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science (2018/2024), Ramsey bounds.