Problem
COM-B2-M06-P020 A Monochromatic Spanning Tree
The edges of the complete graph \(K_n\) are coloured red and blue. Prove that there exists a monochromatic spanning tree, that is, a tree of one colour passing through all \(n\) vertices.
First prove that one of the two colour graphs is connected.
We first prove that either the red or the blue graph is connected. If the red graph is connected, then it has a spanning tree, and that tree is red.
Suppose the red graph is not connected. Then its vertices split into red components. Any edge between different red components is blue; otherwise those components would be one component. Therefore the blue graph is connected: vertices in different red components are joined by blue edges, and two vertices inside the same red component are connected by a blue path of length \(2\) through a vertex from another component.
Thus the blue graph is connected, and every connected graph has a spanning tree. This tree is blue and passes through all vertices.
A strong idea: the forced structure may be a spanning tree, not a clique.