Turkish Mathematical Olympiad

**The answer is $212$.**
Let $K_{2011,2011}$ be a complete bipartite graph in which all vertices of a set $A$ with $|A| = 2011$ are connected to all vertices of $B$ with $|B| = 2011$. We prove that there exists a monochromatic connected subgraph with $212$ vertices if edges of the graph $K_{2011,2011}$ are colored so that all edges incident to any given vertex are colored by at most $19$ colors. Indeed, let $i$$-$th color degree of a vertex $v$ be $d_i(v)$. For each connected pair of vertices $(u, v)$, let us define $f(u, v) = d_i(u) + d_i(v)$ where the edge connecting $u$ and $v$ is colored by the $i$$-$th color. The set of colors used for coloring of all edges incident to $u$ will be denoted by $C(u)$. The Cauchy-Schwarz inequality implies that
$$\frac{1}{2} \sum_{u \in A, v \in B} f(u, v) = \sum_{u \in A, i \in C(u)} d_i^2(u) \geq \left( \sum_{u \in A, i \in C(u)} d_i(u) \right)^2 \cdot \frac{1}{2011 \cdot 19} = 2011^2 \cdot \frac{2011}{19}$$
Therefore, by the pigeon hole principle there exist vertices $s, t$ with $f(s, t) \ge 212$ since $2 \cdot \frac{2011}{19} = 211.68$.
Finally, we give an example with the greatest monochromatic connected component of size $212$ where only $19$ colors are used. Let us partition all vertices of $A$ and $B$ into sets $A_1, \dots, A_{19}$ and $B_1, \dots, B_{19}$ of sizes $105$ or $106$ and color all vertices between $A_i$ and $B_j$ into color $c(i, j)$ where $c(i, j) \equiv i + j \pmod{19}$ and $1 \le c(i, j) \le 19$. It can be readily seen that the maximal monochromatic connected component is of size $212$.