Paper 2, Section II, 17G
(a) Suppose that the edges of the complete graph are coloured blue and yellow. Show that it must contain a monochromatic triangle. Does this remain true if is replaced by ?
(b) Let . Suppose that the edges of the complete graph are coloured blue and yellow. Show that it must contain edges of the same colour with no two sharing a vertex. Is there any for which this remains true if is replaced by ?
(c) Now let . Suppose that the edges of the complete graph 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 are coloured blue and yellow it must contain monochromatic triangles, all of the same colour, with no two sharing a vertex. Is there any for which this remains true if is replaced by ? [You may assume that whenever the edges of the complete graph are coloured blue and yellow it must contain two monochromatic triangles of the same colour with no vertices in common.]