Problem
COM-B2-M06-P005 A Monochromatic Star
#5
★★☆☆☆ Level 2 of 5
Edges from one vertex to \(2m-1\) other vertices are coloured red and blue. Prove that there are \(m\) edges of the same colour.
This is the strengthened pigeonhole principle.
If there are at most \(m-1\) red edges and at most \(m-1\) blue edges, then there are at most \(2m-2\) edges in total. But there are \(2m-1\) edges. Hence one colour appears at least \(m\) times.
This form is often used inside Ramsey proofs.