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 KN thì tồn tại Km xanh hoặc Kn đỏ .
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
Km−1màu xanh hoặc knmàu đỏ .Nếu tồn tại Kn đỏ thì xong,nếu tồn tại Km−1 xanh
thì cùng với A ta có Km 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 Km màu xanh (xong),hoặc Kn−1 màu đỏ thì kết
hợp với A sẽ có Kn màu đỏ .
Vậy R(m,n)≤R(m−1,n)+R(m,n−1).