1 Autumn tournament

There are at least $kmn$ edges colored in the most used color. We delete the remaining edges and prove that there exists a connected component with at least $m+n$ vertices in the remaining graph. The idea is to consider all the connected components. If each one has less than $m+n$ vertices, then the graph is too fragmented and it's impossible to have too many (at least $kmn$) edges even if all edges are present in every connected component. It boils down to prove a certain inequality.

Lemma. Let $x,y$ be two positive real numbers and $\ell ,k$; $\ell \ge k$ be natural numbers. Let $x_i,y_i,i=1,2,\dots ,\ell$ satisfy the following conditions. $$x_i\ge 0,y_i\ge 0,x_i+y_i\le (x+y)/k,i=1,2,\dots ,\ell ;$$ $$\sum _{i=1}^{\ell }{x}_i=x,\sum _{i=1}^{\ell }{y}_i=y.(1)$$ Then it holds $$\sum _{i=1}^{\ell }{x}_i{y}_i\le \frac{xy}{k}.$$ The equality is reached only if $x_i=x/k,y_i=y/k,i=1,2,\dots ,k$; $x_i=y_i=0,i>k$. Proof. Let us denote $f(x,y):={\sum }_{i=1}^{\ell }{x}_i{y}_i$, where $x=(x_1,\dots ,x_{\ell })$, $y=(y_1,\dots ,y_{\ell })$. The conditions in (1) determine a compact set, hence $f$ attains its maximum value on it, say, at the points $x_i^{\prime },y_i^{\prime },i=1,2,\dots ,\ell$. We can assume $x_1^{\prime }\ge x_2^{\prime }\ge \cdots \ge x_{\ell }^{\prime }$. We shall prove that $y_i^{\prime }$ are also in decreasing order. Let us assume on the contrary that $y_i^{\prime }<y_{i+1}^{\prime }$. Set $$x_i=x_{i+1}:=(x_i^{\prime }+x_{i+1}^{\prime })/2;y_i=y_{i+1}:=(y_i^{\prime }+y_{i+1}^{\prime })/2.$$ Then (Chebyshev inequality) $$x_i{y}_i+x_{i+1}{y}_{i+1}>x_i^{\prime }{y}_i^{\prime }+x_{i+1}^{\prime }{y}_{i+1}^{\prime }.$$ But it contradicts the maximality of $x_i^{\prime },y_i^{\prime },i=1,\dots ,\ell$. Next, if $x_1^{\prime }+y_1^{\prime }<(x+y)/k$ we can similarly set $x_1:=x_1^{\prime }+\epsilon ,x_2:=x_2^{\prime }-\epsilon ;y_1:=y_1^{\prime }+\delta ,x_2:=x_2^{\prime }-\delta$ for sufficiently small $\epsilon ,\delta \ge 0$ and get a larger value of $f$. Therefore, $x_1^{\prime }+y_1^{\prime }=(x+y)/k$. Let $k^{\prime }$ be the largest index for which $x_{k^{\prime }}>0$ and $y_{k^{\prime }}>0$. In the same way we can see that $x_i^{\prime }+y_i^{\prime }=(x+y)/k,i=1,2,\dots ,k^{\prime }$. Hence, $k^{\prime }\le k$. Assume that $k^{\prime }<k$ and $y_i=0,i>k^{\prime }$. We modify $x^{\prime },y^{\prime }$ as follows. Set $$\begin{gathered} x_i:=x_i^{\prime },y_i:=y_i^{\prime },i=1,2,\dots ,k^{\prime }-1; \\ {x}_{k^{\prime }}:=x_{k^{\prime }}^{\prime },y_{k^{\prime }}:=y_{k^{\prime }}^{\prime }-\epsilon ,x_{k^{\prime }+1}:=(x+y)/k,y_{k^{\prime }+1}:=\epsilon . \end{gathered}$$ For $i>k^{\prime }+1$ we set $y_i=0$, and the values of $x_i,i>k^{\prime }+1$ are irrelevant providing they comply with (1). Since $x_k^{\prime }<(x+y)/k$, it can be seen that $f(x,y)>f(x^{\prime },y^{\prime })$ which contradicts the maximality of $x^{\prime },y^{\prime }$. Thus, $k^{\prime }=k$. We prove that $x_i^{\prime }=x/k,y_i^{\prime }=y/k,i=1,2,\dots ,k$. Assume on the contrary it doesn't hold and let $j$ be the first index for which $x_j^{\prime }\ne x/k$. WLOG let $x_j^{\prime }<x/k$. Then there exists $i>j$ for which $x_i^{\prime }>x/k$. This means $x_i^{\prime }>x_j^{\prime }$ and thus the sequence $x_1^{\prime },x_2^{\prime },\dots ,x_k^{\prime }$ is not decreasing, contradiction. To recap, we established that $x_i^{\prime }=x/k,y_i^{\prime }=y/k,i=1,2,\dots ,k$. In this case $f(x^{\prime },y^{\prime })=kxy$, and Lemma 1 is proved. $\square$

Back to the problem. The number of all edges of $K$ is $k^{2}mn$, hence there is a color, say, white such that at least $kmn$ edges are colored white. We delete all edges colored in a color other than white. We'll prove that in the remaining graph $K^{\prime }$, there exists a connected component with at least $m+n$ vertices. Assume on the contrary it is not true. Denote the connected components of $K^{\prime }$ by $G(A_i,B_i)$, $i=1,2,\dots ,\ell$ and let $|A_i|=m_i,|B_i|=n_i,i=1,2,\dots ,\ell$. We have $$\sum _{i=1}^{\ell }{m}_i=km,\sum _{i=1}^{\ell }{n}_i=kn,m_i+n_i<m+n.$$ According to Lemma 1, $$\sum _{i=1}^{\ell }{m}_i{n}_i<kmn$$ which contradicts the choice of the white color. This means that for at least one index $i$ it holds $m_i+n_i\ge m+n$.