Problem
COM-B2-M06-P017 One Colour Is Connected
The edges of the complete graph \(K_n\) are coloured red and blue. Prove that either the red graph or the blue graph is connected.
If the red graph is not connected, look at the edges between its components.
If the red graph is connected, we are done. Suppose it is not connected. Then its vertices split into several red components.
Any edge between two different red components cannot be red; otherwise those components would merge. Hence all such edges are blue.
We show that the blue graph is connected. If two vertices lie in different red components, they are joined by a blue edge. If they lie in the same red component, take a vertex from another red component; both edges to it are blue, so there is a blue path of length \(2\). Therefore the blue graph is connected.
This is not a clique, but it is still a forced monochromatic structure.