Question

试证明：对任意正整数m≥3，n≥3，有 r(m，n)≤r(m-1，n)+r(m，n-1)

Answer 1

【答案】：令N=r(m-1，n)+r(m，n-1)，对K_N的边任意进行红、蓝着色，设x是K_N的一个顶点，在K_N中与x相关联的边共有r(m-1，n)+r(m，n-1)-1条。这些边要么为红色，要么为蓝色。由鸽巢原理可知，与x相关联的这些边中，要么至少有r(m-1，n)条红边，要么至少有r(m，n-1)条蓝边。
对于至少有r(m-1，n)条红边的情形，以这些与x相关联的红边的除x外的r(m-1，n)个顶点构成的完全图K_r(m-1，n)中，或者有一个红色K_m-1，或者有一个蓝色K_n。如果有红色K_m-1，则该红色K_m-1加上顶点x以及x与K_m-1之间的红边，就构成一个红色K_m；否则，就有一个蓝色K_n。
对于至少有r(m，n-1)条蓝边的情形，以这些与x相关联的蓝边的除x外的r(m，n-1)个顶点构成的完全图K_r(m，n-1)中，或者有一个红色K_m，或者有一个蓝色K_n-1，若有一个蓝色K_n-1，则该K_n-1加上顶点x以及x与K_n-1之间的蓝边，就构成一个蓝色K_n；否则，就有一个红色K_m。
综合以上两种情况，有
r(m，n)≤N=r(m-1，n)+r(m，n-1)