= 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 \b[$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 \b[$R(3,4)\le9$].
Back to article page
