Paper 2, Section II, 17G

Graph Theory
Part II, 2019

(a) Suppose that the edges of the complete graph K6K_{6} are coloured blue and yellow. Show that it must contain a monochromatic triangle. Does this remain true if K6K_{6} is replaced by K5K_{5} ?

(b) Let t1t \geqslant 1. Suppose that the edges of the complete graph K3t1K_{3 t-1} are coloured blue and yellow. Show that it must contain tt edges of the same colour with no two sharing a vertex. Is there any t1t \geqslant 1 for which this remains true if K3t1K_{3 t-1} is replaced by K3t2K_{3 t-2} ?

(c) Now let t2t \geqslant 2. Suppose that the edges of the complete graph KnK_{n} are coloured blue and yellow in such a way that there are a blue triangle and a yellow triangle with no vertices in common. Show that there are also a blue triangle and a yellow triangle that do have a vertex in common. Hence, or otherwise, show that whenever the edges of the complete graph K5tK_{5 t} are coloured blue and yellow it must contain tt monochromatic triangles, all of the same colour, with no two sharing a vertex. Is there any t2t \geqslant 2 for which this remains true if K5tK_{5 t} is replaced by K5t1K_{5 t-1} ? [You may assume that whenever the edges of the complete graph K10K_{10} are coloured blue and yellow it must contain two monochromatic triangles of the same colour with no vertices in common.]