Paper 4, Section II, F

Graph Theory
Part II, 2011

(i) Given a positive integer kk, show that there exists a positive integer nn such that, whenever the edges of the complete graph KnK_{n} are coloured with kk colours, there exists a monochromatic triangle.

Denote the least such nn by f(k)f(k). Show that f(k)3k!f(k) \leqslant 3 \cdot k ! for all kk.

(ii) You may now assume that f(2)=6f(2)=6 and f(3)=17f(3)=17.

Let HH denote the graph of order 4 consisting of a triangle together with one extra edge. Given a positive integer kk, let g(k)g(k) denote the least positive integer nn such that, whenever the edges of the complete graph KnK_{n} are coloured with kk colours, there exists a monochromatic copy of HH. By considering the edges from one vertex of a monochromatic triangle in K7K_{7}, or otherwise, show that g(2)7g(2) \leqslant 7. By exhibiting a blue-yellow colouring of the edges of K6K_{6} with no monochromatic copy of HH, show that in fact g(2)=7g(2)=7.

What is g(3)?g(3) ? Justify your answer.