= Ramsey number recursion
{c}
{title2=$R(k,\ell)\leq R(k-1,\ell)+R(k,\ell-1)$}
Let $A=R(k-1,\ell)$ and $B=R(k,\ell-1)$. From one vertex of any red-blue colored $K_{A+B}$, either at least $A$ incident edges are red or at least $B$ are blue. In the first case, apply the definition of the <Ramsey number> to its red neighbors: a red $K_{k-1}$ extends with the chosen vertex, and a blue $K_\ell$ is already enough. The blue case is analogous. This proves the recursion, with boundary values $R(k,2)=k$ and $R(2,\ell)=\ell$.
Back to article page
