Bài 5

Lấy $t=r(m-1,n-1)+3$ người. Nếu cả $t$ người đôi một quen nhau, chọn $2m$ người. Nếu không có cặp nào quen nhau, chọn $2n$ người. Trường hợp còn lại, tồn tại ba người $u,v,w$ sao cho $u,v$ quen nhau còn $u,w$ không quen nhau. Bỏ ba người này; trong $r(m-1,n-1)$ người còn lại có hoặc $m-1$ cặp quen nhau hoặc $n-1$ cặp không quen nhau. Thêm cặp $uv$ ở trường hợp đầu hoặc $uw$ ở trường hợp sau, suy ra $r(m,n)\le r(m-1,n-1)+3$.