c) Trước hết ta chứng minh bất đẳng thức sau $R(m,n) ≤ R(m − 1,n) + R(m,n − 1)$.
Ta xét $N = R(m − 1,n) + R(m,n − 1)$.
Ta sẽ chứng minh mọi cách tô màu các cạnh của $K_N$ thì tồn tại $K_m$ xanh hoặc $K_n$ đỏ .
Xét đỉnh A bất kì thì $N − 1 = R(m − 1,n) + R(m,n − 1) − 1$
Đỉnh còn lại sẽ kề với A bởi các cạnh màu xanh hoặc màu đỏ .
* Trường hợp 1:
Hoặc có $≥ R(m − 1,n)$ đỉnh nối với A bởi màu xanh.
* Trường hợp 2:
Hoặc có $≥ R(m,n − 1)$ đỉnh nối với A bởi màu đỏ .
Ta xét cụ thể các trường hợp như sau:
Trường hợp 1:
Với mọi cách tô màu tập X(A) bằng các đỉnh kề với A bởi 1 cạnh X ,thì sẽ tồn tại
$K_{m−1}$màu xanh hoặc knmàu đỏ .Nếu tồn tại $K_n$ đỏ thì xong,nếu tồn tại $K_{m−1}$ xanh
thì cùng với A ta có $K_m$ xanh.
.
Trường hợp 2:
$D(A)$ là tập các đỉnh kề với A bởi 1 cạnh đỏ ,và $D(A) ≥ R(m,n− 1)$,thì với mọi
cách tô màu của $D(A)$ nếu tồn tại $K_m$ màu xanh (xong),hoặc $K_{n−1}$ màu đỏ thì kết
hợp với A sẽ có $K_n$ màu đỏ .
Vậy $R(m,n) ≤ R(m − 1,n) + R(m,n − 1)$.