= Solution
Put $A=R(k-1,\ell)$, $B=R(k,\ell-1)$ and consider any coloring of $K_{A+B}$. Choose a vertex $v$. Among its $A+B-1$ neighbors, either at least $A$ are joined to it by red edges, or at least $B$ by blue edges.
In the red case, the induced <complete graph> on those neighbors contains either a red $K_{k-1}$, which joins with $v$ to make a red $K_k$, or a blue $K_\ell$. The blue case similarly gives a red $K_k$ or a blue $K_{\ell-1}$ which extends with $v$ to a blue $K_\ell$. Hence every coloring has the required configuration, and
$$
\boxed{R(k,\ell)\leq R(k-1,\ell)+R(k,\ell-1).}
$$
This is the <Ramsey number recursion>.
Back to article page
