Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours
Marina Drygala
- 75
- 3