Ramsey定理 定理设,q为正整数,p,q≥2,则存在最小正整 数R(,q),使得当n≥R(D9)时,用红蓝两色涂 色Kn的边,则或存在一个蓝色的En,或存在 个红色的K矿 证明思路:归纳法 归纳假设R(D,2)≤,R2,q)≤, 归纳步骤R(p-1,q,R(q-1,p)存在 =R(P, sR(P-1,+R(q-1,p)5 Ramsey定理 定理 设 p, q为正整数，p, q ≥ 2，则存在最小正整 数R(p, q)，使得当 n ≥ R(p,q) 时，用红蓝两色涂 色Kn 的边，则或存在一个蓝色的 Kp，或存在一 个红色的 Kq. 证明思路：归纳法 归纳假设 R(p, 2)≤p, R(2, q)≤q, 归纳步骤 R(p-1, q)，R(q-1, p)存在 ⇒ R(p,q) ≤ R(p-1, q) + R(q-1, p)