首先明确拉姆塞数的核心定义：( R(k,m) ) 是满足以下条件的最小正整数 ( n )：对任意 ( n ) 顶点完全图 ( K_n ) 进行红蓝边染色，图中要么存在红色的 ( K_k ) 子图，要么存在蓝色的 ( K_m ) 子图。

已知 ( A = R(k,m-1) )、( B = R(k-1,m) ) 均为偶数，我们通过反证法结合图论基本性质来完成证明：

步骤1：设定目标图并分析顶点度数 #

令 ( n = A+B-1 )，取任意一个 ( n ) 顶点的完全图 ( K_n ) 进行红蓝边染色。任取图中一个顶点 ( v )，定义：

• ( r )：( v ) 连出的红色边数量（即 ( v ) 的红色邻居数）
• ( b )：( v ) 连出的蓝色边数量（即 ( v ) 的蓝色邻居数）

显然有 ( r + b = n-1 = (A+B-1)-1 = A+B-2 )。

步骤2：反证法假设 #

假设该染色后的 ( K_n ) 中既不存在红色 ( K_k )，也不存在蓝色 ( K_m )，我们将基于此推出矛盾。

步骤3：约束邻居子图的大小 #

• 对于 ( v ) 的蓝色邻居子图：
  因为 ( A = R(k,m-1) )，如果 ( b \geq A )，根据拉姆塞数定义，这个子图中要么存在红色 ( K_k )（与假设矛盾），要么存在蓝色 ( K_{m-1} )——此时加上 ( v ) 与这些邻居的蓝色边，就构成了蓝色 ( K_m )（同样矛盾）。因此必有 ( b \leq A-1 )。

• 对于 ( v ) 的红色邻居子图：
  同理，因为 ( B = R(k-1,m) )，如果 ( r \geq B )，这个子图中要么存在红色 ( K_{k-1} )（加上 ( v ) 与这些邻居的红色边，构成红色 ( K_k )，矛盾），要么存在蓝色 ( K_m )（矛盾）。因此必有 ( r \leq B-1 )。

步骤4：推导奇偶性矛盾 #

结合 ( r + b = A+B-2 ) 和上述两个不等式，可得：
[ r + b \leq (B-1) + (A-1) = A+B-2 ]
等号必须成立，因此 ( r = B-1 )，( b = A-1 )。

现在分析度数的奇偶性：

• ( A ) 是偶数，所以 ( b = A-1 ) 是奇数；
• ( B ) 是偶数，所以 ( r = B-1 ) 是奇数；
• ( n = A+B-1 ) 是偶数+偶数-1=奇数，即图中有奇数个顶点。

考虑红色子图的总度数：奇数个奇数相加的结果是奇数，但根据图论基本定理，任何图的总度数必为偶数（每条边贡献2度），这就产生了矛盾！

步骤5：结论 #

我们的假设不成立，因此 ( n = A+B-1 ) 满足拉姆塞数的定义，即 ( R(k,m) \leq A+B-1 )。

内容的提问来源于stack exchange，提问作者Arnab Mukherjee