下面证明R(K,K)≤9.为了建立这个不等式，我们会证明K r(K3,K4)≤9 的每个红-蓝着色中要么包含红K,要么包含蓝K,假设给出了K, 的一个红~蓝着色，首先考虑K,红子图，它不可能是3-正则图，因为 任何图中奇阶顶点的个数不能是奇数.因此，K,中的某个顶点)不 能恰好与三条红色边相关联，我们分下面两种情况考虑 情况1顶点v与四条或者更多的红边相关联.此时，K,中存在 4个顶点1、2、、满足边m1、w2、m、w,都是红色的.如果 集合A={,2,,}中的任意两个顶点连成红色的边，那么就 生成了红K；否则，A中任意两个顶点用蓝色边连结，就会产生 蓝K 情况2顶点v与两个或更少的红边相关联.此时，v与六条或 者更多蓝边相关联。因此在K,中存在顶点山1,2，…，6，满足边 1,2,…,u6是蓝色的.因为R(K,K)=6,顶点集{山1， 山2，·，6}的导出子图H=K6,它要么包含红K,要么包含蓝K 如果H包含一个红K,那K,也包含红K,如果H包含一个蓝K, 又因为)和H中的每个顶点连线都是蓝色，所以K,就包含一个 蓝K4 因此，在上述两种情况中，K,的红-蓝着色导致了要么形成一个 红K,要么形成一个蓝K·◆ 3 4 r K K ( , ) 9 