62nd Ukrainian National Mathematical Olympiad

Suppose we have a complete graph with each edge colored in one of three colors. We show that there will always exist a connected component of at least one of the colors of size at least $1012$. First, we show that it is possible to color the edges in such a way that connected components of size more than $1012$ vertices do not exist. Let's label the colors with numbers - 1st, 2nd and 3rd. Let's divide the vertices into groups by $506$ - groups "A", "B", "C" and "D". Let all $1012$ vertices of groups "A" and "B" be connected by edges of color 1, all vertices of group "C" - by color 2, group "D" - by color 3. Between them, all vertices are connected by edges of those colors, as shown in fig. 20. Therefore, groups "A" or "B" form a connected component of size $1012$ of color 1. Groups "A" and "C" are of color 2, groups "B" and "D" are of color 3. Obviously, there is no larger connected component in terms of the number of vertices.

Suppose that there exists a coloring such that the largest connected component contains fewer than $1012$ vertices. Let's consider the coloring that gives the smallest answer to the problem.

Consider the largest connected component of one of the colors. This component, or rather the number of vertices in it, is the answer to the problem. If there are several largest components, choose any of them. Let this component correspond to color 1. Let's denote this component as I. Let this component contain exactly $m$ vertices. Note that not all the edges between the vertices of this component have the color 1. But if we repaint all the edges of this component with color 1, then the answer $m$ in the problem will not change. In this case, there are no vertices of the component I from which an edge of color 1 can come out outside this component I, that is, to a vertex that does not belong to the component I.

Next, consider the largest connected component among all other vertices, II, with color 2 or 3. It includes all the vertices that are connected by color 2, i.e., also those that can be reached through the vertices of the component I. For example, if $A\in$ II, $B\in$ I, and for the vertex $C\notin$ I the following conditions are true: $A(II)2\leftrightarrow B(I)2\leftrightarrow C$, then we assume that $C\in$ II, but we do not assume that $B\in$ II. In other words, a vertex cannot belong to two components at the same time (this principle will be maintained in the future). The number of vertices in the component II is denoted by $k$. Now we can repaint all edges in this component into color 2, and, again, the answer $m$ in the problem will not change.

Now let's denote by $X_2$ the group of vertices of the component I that are connected to at least one vertex of the component II by an edge of color 2, let their number be $x_2$. Then all the edges between the vertices $X_2$ and the vertices of component II can be colored in color 2. They still form the connected component of color 2 before this coloring, but since the component of color 1 was chosen first, the total number of vertices $k+x_2\le m$.

Then all the vertices of the component I that are not included in the group $X_2$, we will combine into the group $X_3$ and denote their number by $x_3$. From these vertices, only edges of color 3 can go to each vertex of component II. But then the vertices of the group $X_3$ and the component II form a connected component of color 3. But then from the vertices of the group $X_3$ there cannot be any edges of color 1 or 3 to vertices that are not included in the components I and II. If there is an edge of color 3, then the connected component of color 3 will be larger than the component II, and this contradicts its construction. Therefore, all vertices that are not included in the components I and II are connected by color 2 (since $X_3$ is not empty). We denote all these vertices as a component III. Similarly, the vertices of the group $X_2$ are connected with III only with edges of color 3. But then the components II and III should be connected only by edges of color 1. That is, they form a connected component of color 1. But we initially chose the largest connected component of color 1, which has $m$ vertices. Therefore, groups II and III groups have no more than $m$ vertices, hence $2m\ge 2024$ and this completes the proof.