Bulgarian Winter Tournament

We need to prove that in a complete graph with $n$ vertices and $k$ colors, where the induced graph on each color is connected, there exists a multicolor triangle. Denote the colors by $1$, $2$, $3$, $\dots$, $k$ and recolor all edges that are in any of the colors $4$, $5$, $\dots$, $k$ into color $3$. The new graph satisfies the condition of connectivity on each color and if there is a multicolored triangle for it, then the same triangle in the initial graph will also be multicolored. Therefore, we can consider that $k=3$.

Suppose that the statement is not true for a graph $G$, as we can choose $G$ to have a minimal number of vertices. It follows from the minimality of $G$ that after removing any vertex, the new graph will not be connected by any of the colors, and let it be color $1$. Denote by $G_1,G_2,\dots ,G_t$ the color connectivity components $1$ after deleting vertex $A$. Since $G$ is color $1$ connected, there exist $A_i\in G_i$ for which $A{A}_i$ is color $1$. The segment $A_1{A}_2$ is not color $1$ because $G_1$ and $G_2$ are different components of connectivity. Let it be of color $2$. If $A_{1}B$ is a color $1$ segment of $G_1$, then the segment $A_{2}B$ cannot be of color $1$ because $G_1$ and $G_2$ are different connectivity components; cannot be of color $3$, because then $A_1{A}_{2}B$ is a multicolor triangle and is therefore of color $2$. Analogously, it is proved that all segments between the points of $G_1$ and $G_2$ are of color $2$. We obtained that all segments between any two connectivity components are either color $2$ or color $3$.

Now consider segments $AX$ and $AY$ in colors $2$ and $3$, respectively (such segments exist, since $G$ is connected in each of the colors). Without limitation, we have the following two cases:

1. $X,Y\in G_1$, then one of the triangles $AX{A}_2$ and $AY{A}_2$ is multicolored.

2. $X\in G_1$ and $Y\in G_2$, then one of the triangles $AX{A}_2$ and $AY{A}_1$ is multicolored.

The resulting contradiction shows that for every graph with the given properties there exists a multicolored triangle. $\square$