Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / A / 3

The Ramsey number $R(s,t)$ is the least $N$ such that every $N$-vertex graph contains a clique of size $s$ or an independent set of size $t$. Take $N=R(s-1,t)+R(s,t-1)$ and choose a vertex $v$. Among its $N-1$ other vertices, either it has at least $R(s-1,t)$ neighbours or it has at least $R(s,t-1)$ nonneighbours.

In the first case those neighbours contain an independent $t$-set or an $(s-1)$-clique, which joins $v$ to form an $s$-clique. In the second case the nonneighbours contain an $s$-clique or an independent $(t-1)$-set, which joins $v$ to form an independent $t$-set. This proves

The five-cycle and its complement both have no triangle, so $R(3,3)>5$. In a six-vertex graph, any vertex has at least three neighbours or three nonneighbours. In the first triple an edge completes a triangle with the chosen vertex, while no edges give an independent triple. The complementary argument handles three nonneighbours. Hence $R(3,3)=6$.

Now suppose a nine-vertex graph contains no triangle and no independent four-set. Each vertex has at most three neighbours, since its neighbourhood is independent. It cannot have at most two neighbours: its at least six nonneighbours contain, by the result just proved, either a triangle or an independent triple; the former is forbidden and the latter joins the vertex to give an independent four-set. Every degree must therefore equal three. But nine vertices of degree three have odd total degree, contradicting the handshake lemma. Thus $R(3,4)\le 9$.

The graph Ramsey number $R(G,H)$ is the least $N$ such that every red-blue coloring of the edges of $K_N$ contains a red copy of $G$ or a blue copy of $H$. Copies are ordinary subgraphs, not necessarily induced. Equivalently every graph on $N$ vertices contains $G$ or its complement contains $H$.

Assume the usual nontrivial case $\chi (G)\ge 2$ and $|H|\ge 2$. On $(\chi (G)-1)(|H|-1)$ vertices partition into $\chi (G)-1$ equal classes of size $|H|-1$. Color all edges between distinct classes red and all edges within a class blue. The red graph is $(\chi (G)-1)$-colorable, so it contains no copy of $G$. Every blue connected component has only $|H|-1$ vertices, so connectedness prevents a blue copy of $H$. Therefore one more vertex is necessary:If $G$ is edgeless or $H$ has one vertex, the displayed lower bound is just one and holds directly.