Given a complete bipartite graph on $n$, $n$ vertices (call this $K_{n,n}$), we colour all its edges using two colours, red and blue. What is the least value of $n$ such that for any colouring of the edges of this graph, there will exist at least one monochromatic $4$-cycle?
This is a question from a high school advanced math exam in india (STEMS 2022 - Tessellate CMI). I was trying this question but I've got nothing worth telling or extremely non-trivial. I have studied graph theory but I havent practiced a lot of it, especially no proof based questions, that's probably why I'm not able to do much progress. If someone can share a solution, It will be great.
Let one part be $\{\,v_1, v_2, \ldots, v_n\,\}$ and another part be $\{\,u_1, u_2, \ldots, u_n\,\}$.
Let's show that for $n = 5$ the graph always has a monochromatic $4$-cycle. Suppose the opposite. Among edges $v_1u1, v_1u_2, \ldots, v_1u_5$ at least $\lceil 5 / 2\rceil = 3$ have the same color. Without loss of generality edges $v_1u_1$, $v_1u_2$ and $v_1u_3$ are red. Since there is no monochromatic $4$-cycle, at least $2$ of edges $v_ku_1$, $v_ku_2$ and $v_ku_3$ are blue for all $k = 2, 3, 4, 5$. Again without loss of generality $v_2u_1$ and $v_2u_2$ are blue. Then $v_ku_3$ and exactly one of $v_ku_1$ and $v_ku_2$ are blue for $k = 3, 4, 5$. It means that for two of such $v_k$'s ($3 \le k \le 5$) blue edges go to $u_3$ and the same $u_i$ ($1 \le i \le 2$). Thus $K_{5, 5}$ always has a monochromatic $4$-cycle.
To show that $n = 5$ is minimum possible let's color $K_{4, 4}$ such that it will not have a monochromatic $4$-cycle: edges $v_1u_1$, $v_1u_2$, $v_2u_1$, $v_2u_3$, $v_3u_2$, $v_3u_4$, $v_4u_3$ and $v_4u_4$ are red, all other edges are blue. It is easy to see that each vertex has $2$ red and $2$ blue edges, and for each $v_i$ set of ends $u_j$ of red edges is unique. The same with blue edges.