Problem
COM-B2-M06-P010 A Large Monochromatic Star
#10
★★★☆☆ Level 3 of 5
In the complete graph \(K_{2m}\), the edges are coloured red and blue. Prove that there is a vertex from which at least \(m\) edges of one colour leave.
Take any vertex.
From any vertex, \(2m-1\) edges leave. By the strengthened pigeonhole principle, among these edges there are at least \(m\) edges of one colour. Thus any vertex works.
A simple but frequently used star form of Ramsey reasoning.