= Solution
The <graph Ramsey number> $R(s,t)$ is the least $N$ for which every <graph> on $N$ vertices has a <clique> of size $s$ or an <independent set> of size $t$; $R(s)=R(s,s)$ is the <diagonal Ramsey number>. The base cases are $R(2,t)=t$ and $R(s,2)=s$.
Assume the smaller parameters already have finite <graph Ramsey numbers>, and take $N=R(s-1,t)+R(s,t-1)$. For any vertex, either its neighbourhood has at least $R(s-1,t)$ vertices, or its nonneighbourhood has at least $R(s,t-1)$ vertices. In the first case it contains an independent $t$-set, or an $(s-1)$-clique which extends with the chosen vertex. In the second it contains an $s$-clique, or a $(t-1)$-independent set which extends with that vertex. Induction proves existence and
$$
\boxed{R(s,t)\leq R(s-1,t)+R(s,t-1).}
$$
Back to article page
