Past exam of the mathematics course of the University of Cambridge / 2011 / ii / Paper 4 / 17F / i / Solution

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.