Problem
COM-B2-M06-P019 Three Colours on \(17\) Vertices
The edges of the complete graph \(K_{17}\) are coloured in three colours. Prove that there exists a monochromatic triangle.
From one vertex, \(16\) edges leave. Find \(6\) edges of one colour.
Choose a vertex \(v\). From it, \(16\) edges leave in three colours, so by the pigeonhole principle at least \(6\) of them have one colour. Let these be red edges to a set \(A\) of \(6\) vertices.
If there is a red edge inside \(A\), it forms a red triangle together with \(v\). If there are no red edges inside \(A\), then all edges inside \(A\) are coloured with the two remaining colours.
By \(R(3,3)=6\), every two-colouring of the edges on \(6\) vertices contains a monochromatic triangle. It is monochromatic in one of the two remaining colours. Hence the original three-colouring also contains a monochromatic triangle.
A first careful example of multicolour Ramsey reasoning.