= Solution
The <Ramsey number> $R(s,t)$ is the least <integer> $N$ such that every <graph> on $N$ <vertices> contains either a <clique> of size $s$ or an <independent set> of size $t$. Equivalently, every red-blue <colouring> of the <edges> of $K_N$ contains a red $K_s$ or a blue $K_t$.
Put $a=R(s-1,t)$, $b=R(s,t-1)$ and consider a <graph> on $a+b$ <vertices>. Fix a <vertex> $v$. If it has at least $a$ <neighbours>, their induced <graph> contains either a <clique> of size $s-1$, which together with $v$ gives a <clique> of size $s$, or an <independent set> of size $t$. Otherwise $v$ has at least $b$ nonneighbours. Their induced <graph> contains either a <clique> of size $s$, or an <independent set> of size $t-1$, which can be enlarged by $v$. Thus
$$
\boxed{R(s,t)\leq R(s-1,t)+R(s,t-1).}
$$
Since $R(2,3)=R(3,2)=3$, this gives $R(3,3)\leq6$. For the reverse bound, the <cycle graph>[five-cycle] has no <triangle in a graph>[triangle] and no <independent set> of size three: its <complement> is again a <cycle graph>[five-cycle], so it too is triangle-free. Hence the property fails on five <vertices> and
$$
\boxed{R(3,3)=6.}
$$
\Image[/past-exam-of-the-graph-theory-course-of-the-university-of-oxford/2011-ramsey-five-cycle.png]
{title=The five-cycle and its complement witness the lower bound for R(3,3)}
{description=Both panels use the same five labelled vertices. The red cycle and the blue complementary edges are each triangle-free; crossings in the right panel are not vertices.}
Back to article page
