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
Here is a short proof. Thanks to David Speyer for simplifying an earlier proof of mine (see the comments below).


For each colour $i \in [n]$, let $a\_i$ be the number of vertices incident to an edge of colour $i$. Observe that $a\_i \geq 2\sqrt{n}$ for all $i$, where equality is obtained if and only if the edges of colour $i$ induce a $K\_{\sqrt{n}, \sqrt{n}}$. Thus, $\sum\_{i \in [n]} a\_i \geq 2n \sqrt{n}$. On the other hand, $\sum\_{i \in [n]} a\_i$ is the number of ordered pairs $(v,i)$, where $v$ is a vertex, and $i$ is a colour incident to $v$. Therefore, since there are only $2n$ vertices, some vertex must be incident to at least $\sqrt{n}$ colours.


