Return to Revisions

For each colour $i \in [n]$, let $r_i$ be the number of vertices incident to an edge of colour $i$ on the right side of $K_{n,n}$ and $\ell_i$ be the number of vertices incident to an edge of colour $i$ on the left side of $K_{n,n}$. Observe that $r_i+\ell_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}}$. Now for each colour $i$ choose a subgraph $R_i$ of the edges of colour $i$ such that there are $r_i$ vertices of $R_i$ on the right and each vertex on the right has degree $1$. Similarly, let $L_i$ be a subgraph of the edges of colour $i$ such that there are $\ell_i$ vertices of $L_i$ on the left and each vertex on the left has degree $1$. Since $r_i+\ell_i \geq 2\sqrt{n}$ for all $i$, we must have that $\bigcup_{i \in [n]} R_i$ has a vertex on the right with degree at least $\sqrt{n}$, or $\bigcup_{i \in [n]} L_i$ has a vertex on the left with degree at least $\sqrt{n}$. In either case we have found a vertex incident to at least $\sqrt{n}$ colours.