The answer is $1012.$ So, we have a complete graph $K$ which edges are colored in 3 colors. We take the number of vertices of the maximum connected monochromatic subgraph. The question is to find the possible minimum of this value when we vary colors. The following claim has a standalone value. Claim. Let $K_{m,n}$ be a complete bipartite graph with parts of $m$ and $n$ vertices. Its edges are colored in two colors. Then there exists a connected subgraph with edges of the same color with at lest $(m+n)/2$ vertices. Proof. Let $A,B$ be the partitions of the vertices, $|A|=m, |B|=n$ and the colors be white and black. For any $a\in A,$ by $d_w(a)$ we denote the number of white edges incident with $a$ and $d_b(a)$ denotes the number of corresponding black edges. Suppose wlog $\sum_{a\in A}d_w(a)\ge \sum_{a\in A}d_b(a).$ It means $$\sum_{a\in A}d_w(a) \ge mn/2.$$We delete the black edges. Let the connected components of the remaining graph consist of $(m_1,n_1),(m_2,n_2),\dots,(m_k,n_k)$ vertices. Arguing by contradiction, assume $$m_i+n_i<\frac{m+n}{2} \qquad (1)$$We have $$\sum_{i=1}^k m_i n_i\ge \frac{mn}{2}$$It can be seen that under the conditions $(1)$ and $\sum_i m_i=m, \sum_i n_i=n$ it holds $$\sum_{i=1}^k m_i n_i< \frac{mn}{2}$$contradiction. $\square$ Back to the original problem. Let $K$ be a complete graph of order $4n, n\in\mathbb{N}.$ Take the largest possible monochromatic component, and its color be, say, white. Let $V$ be its vertex set. Assume $ |V|<2n.$ Let $V':=V(K)\setminus V.$ Consider the induced bipartite graph on the parts $V, V'.$ There is no edge between $V$ and $V'$ colored in white, because we took the maximum component. By the above claim, there is a connected monochrome subgraph with at least $4n/2=2n$ vertices, which contradicts the maximality of $V.$ It, remains to construct a coloring of $K_{4n}$ with maximum monochrome subgraph of exactly $2n$ vertices. Group the vertices in 4 groups $A_1,A_2,B_1,B_2,$ each of $n$ vertices. Color edges as follows: in white - those between $A_1$ and $A_2$ as well as between $B_1$ and $B_2;$ in black - between $A_1$ and $B_1$ and between $A_2$ and $B_2$; in red - between $A_1$ and $B_2$ and between $A_2$ and $B_1.$

Here is an alternative proof of @dgrozev's lemma. By Pigeonhole, there is a collection of $e \geq \frac{mn}{2}$ edges of the same colour. We claim that the induced subgraph $H$ by this collection satisfies the requirements. It suffices to show that there exist vertices $a$ and $b$ with $\deg a + \deg b \geq \frac{m+n}{2}$, as then component formed by $a$, $b$ and their neighbours would satisfy the requirements. To do that, we will sum globally (i.e. throughout the whole graph) and rely on Pigeonhole. We have $\sum_{a\in A} \sum_{b\in B} (\deg a + \deg b) = |B| \sum_{a\in A} \deg a + |A| \sum_{b\in B} \deg b = |B| \cdot e + |A| \cdot e \geq \frac{mn}{2}(m+n)$. Since the number of pairs $(a,b)$ is $mn$, there is a pair with sum of degrees at least $\frac{m+n}{2}$, done!

@above: Nice try! What you proved is that there exists a pair of vertices $(a,b)$ with $\deg(a) + \deg(b)\ge (m+n)/2$ which is next to trivial. What you have to prove is that there exists a pair $(a,b)$ connected with an edge such that $\deg(a) + \deg(b)\ge (m+n)/2$. Only then you can claim that $a$ and $b$ are in the same connected component. Fortunately, this idea can be carried out, but you need to sum $\deg(a) +\deg(b)$ over all edges.

@dgrozev ooof, thanks a lot! Here is the fix along the approach you suggested, it took me some headaches to correct errors, but I agree it's easy. Similarly to before, we desire $\deg a + \deg b \geq \frac{m+n}{2}$ for an edge $ab$ and so we should sum globally over all edges and apply Pigeonhole. As usual, denote $V$ as the set of vertices and $E$ as the set of edges. We have $\sum_{ab \in E} (\deg a + \deg b) = \sum_{x \in V}(\deg x)^2$ since in the former sum each $\deg a$ is counted $\deg a$ times (as $a$ is incident with $\deg a$ edges). Now, $\sum_{x \in V}(\deg x)^2 = \sum_{a\in A}(\deg a)^2 + \sum_{b\in B}(\deg b)^2$ and by the inequality between Quadratic mean and Arithmetic mean this is at least $\frac{(\sum_{a\in A} \deg a)^2}{m} + \frac{(\sum_{b\in B} \deg b)^2}{n}$. The sums in both numerators equal the number of edges (note that the graph is bipartite) which is $e \geq \frac{mn}{2}$, so overall we have $\frac{e^2(m+n)}{mn}$ as a lower bound. Now by Pigeonhole there is an edge $ab$ with sum of degrees at least $\frac{e(m+n)}{mn} \geq \frac{m+n}{2}$, done!