Past exam of the mathematics course of the University of Cambridge / 2011 / ii / Paper 4 / 17F (Graph Theory)

With one edge colour, $f(1)=3$. Suppose the assertion is known for $k-1$ colours, and take $n=k(f(k-1)-1)+2$. At any vertex, among its $n-1$ incident edges some colour occurs on at least $f(k-1)$ edges. Let $S$ be their other endpoints. If an edge within $S$ has that colour, it completes a monochromatic triangle with the chosen vertex. Otherwise $S$ uses only $k-1$ colours internally, and the inductive hypothesis gives a monochromatic triangle there. ThusInduction now yieldsTogether with the base case, $\boxed{f(k)\le 3k!}$ for every positive $k$. This is a constructive multicolour Ramsey bound.

In any two-colouring of $K_7$, there is a monochromatic triangle because $f(2)=6$. Call its colour blue. If any edge from one of its vertices to an outside vertex is blue, the triangle and that edge give the required copy of $H$. Otherwise all edges from that triangle to the four outside vertices are yellow. If any edge among those four is yellow, it makes a yellow triangle with a vertex of the original triangle, and another incident yellow edge supplies the pendant edge. If none is yellow, the four outside vertices form a blue $K_4$, which also contains $H$. Hence $g(2)\le 7$.

For the lower bound, divide six vertices into two triples. Colour edges inside each triple blue and all cross-edges yellow. Each blue component is only a triangle, and the yellow graph is bipartite, so neither colour contains $H$. Therefore $\boxed{g(2)=7}$. Copies are not required to be induced: an additional edge in a monochromatic $K_4$ does not invalidate the copy of $H$.

For three colours, $f(3)=17$ supplies a triangle in $K_{17}$. If it has no pendant edge of the same colour, each of its vertices has fourteen edges to outside vertices in the other two colours. Choose one vertex $v$ and a colour occurring on at least seven of those edges, with endpoint set $S$. If an internal edge of $S$ has this colour, it creates a triangle with $v$ and a fourth neighbour supplies the pendant edge. Otherwise $S$ is internally two-coloured, and $g(2)=7$ supplies $H$. Thus $g(3)\le 17$. Conversely the definition $f(3)=17$ ensures a three-colouring of $K_{16}$ without any monochromatic triangle, and therefore without $H$. Hence $\boxed{g(3)=17}$.