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

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$.