Định lý 3: Định lý Ramsey Với mọi số nguyên dương $k, l$ tồn tại một số nguyên dương nhỏ nhất $R(k,l)$ thỏa mãn: Mọi cách tô màu các cạnh của một đồ thị đầy đủ trên $R(k,l)$ đỉnh bằng hai màu xanh và đỏ đều chứa một dồ thị con đầy đủ trên $k$ đỉnh màu xanh hoặc một đồ thị con đầy đủ trên $l$ đỉnh màu đỏ. Chứng minh: Ta chứng minh kết quả mạnh hơn: $R(k,l)$ hữu hạn và $$R(s,t) \le R(s-1,t) + R(s,t-1)\ \forall s,t \ge 2$$
Đặt $N=R(s-1,t)+R(s,t-1)$. Xét một cách tô màu xanh - đỏ các cạnh của một đồ thị $K_N$. Gọi A là một đỉnh bất kì. Trong $N-1$ cạnh kề A có không ít hơn $R(s-1,t)$ cạnh màu xanh hoặc $R(s,t-1)$ cạnh màu đỏ.
Giả sử có $R(s-1,t)$ cạnh màu xanh kề A. Các đầu mút khác A của các cạnh này tạo một đồ thị đầy đủ trên $R(s-1,t)$ đỉnh. Theo quy nạp, đồ thị này chứa hoặc một đồ thị con $K_{s-1}$ với các cạnh đỏ hoặc một đồ thị con $K_t$ với các cạnh xanh. Trong trường hợp đầu, lấy thêm đỉnh A ban đầu ta có đồ thị con $K_s$ đỉnh với các cạnh màu đỏ.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]