Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 2 / 17H / Solution

Let $R(s,t)$ be the two-colour clique Ramsey number. At a vertex of $K_{R(s-1,t)+R(s,t-1)}$, either its red neighbourhood has at least $R(s-1,t)$ vertices or its blue neighbourhood has at least $R(s,t-1)$. In the first case a red $(s-1)$-clique extends through the vertex, or there is a blue $t$-clique; the second case is symmetric. HenceWith $R(1,t)=R(s,1)=1$, induction and Pascal's identity give $R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$. Taking $s=t$ provesThe four-vertex graph is the paw graph, a triangle with a pendant edge; the copy need not be induced. For the lower bound, colour two disjoint triangles in $K_6$ red and all edges between them blue. Red components have only three vertices and blue is bipartite, so neither colour contains a paw. Thus $R(H)\ge 7$.

For the upper bound, $R(3,3)\le 6$ guarantees a monochromatic triangle in $K_7$, say red on a vertex set $T$. A red edge from $T$ to any outside vertex immediately supplies a red paw. Otherwise all edges from $T$ to the remaining four vertices are blue. If those four vertices contain a blue edge $ab$, then $a,b$ and any vertex of $T$ form a blue triangle, and another vertex of $T$ joined to $a$ supplies its pendant edge. If they contain no blue edge, they are a red $K_4$, which contains a red paw. Therefore