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).