Given a fixed edge colouring of $K_{n,n}$ that uses each colour exactly n times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
Any edge colouring of $K_{n,n}$ has a vertex with at least $\sqrt{n}$ incident edges of different colours
Marina Drygala
- 75
- 3