2.II.17H

Graph Theory
Part II, 2007

The Ramsey number R(G)R(G) of a graph GG is the smallest nn such that in any red/blue colouring of the edges of KnK_{n} there is a monochromatic copy of GG.

Show that R(Kt)(2t2t1)R\left(K_{t}\right) \leqslant\left(\begin{array}{c}2 t-2 \\ t-1\end{array}\right) for every t3t \geqslant 3.

Let HH be the graph on four vertices obtained by adding an edge to a triangle. Show that R(H)=7R(H)=7.