Past exam of the short options course of the University of Oxford / 2014 / 6 / b

The Ramsey number $R(k,\ell )$ is the least positive integer $N$ such that every red-blue coloring of the edges of $K_N$ has a red $K_k$ or a blue $K_{\ell }$. Equivalently, every $N$-vertex graph has a clique of size $k$ or an independent set of size $\ell$.

For $N=k$, either there is a blue edge or every edge is red, producing the red $K_k$. Conversely an entirely red $K_{k-1}$ has neither a red $K_k$ nor a blue edge. Therefore

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, andThis is the Ramsey number recursion.

Fix $w\in W$. It has five incident edges, so three of them have the same color by the pigeonhole principle. Suppose they are red, with other endpoints $a,b,c$. Any existing edge among $a,b,c$ must be blue, or it would complete a red triangle with $w$.

If all three edges among $a,b,c$ existed, they would therefore form a blue triangle. Thus their triple must contain the unique missing edge $uv$. In particular, both $u$ and $v$ belong to the three red neighbors, so $wu$ and $wv$ are both red. The identical argument works if the chosen three edges are blue.

Therefore $wu$ and $wv$ have the same color for every $w\in W$. The missing edge is crucial: it is the only way the monochromatic neighbor triangle can fail to be present.