We are given a $k$-edge-colored $K_{kn,km}$ and we want to show that there exists a monochromatic connected component with at least $m+n$ vertices. Choose the most abundant color, which occurs at least $kmn$ times. We will only work with this color from now on. We will denote by $u\sim v$ the fact that there is an edge between $u,v.$ As in the original statement, call the sides of the partition $A{}$ and $B{}$. If there exist $u\sim v$ with $\deg u+\deg v\geqslant m+n$ we're done. Hence, $\deg u+\deg v<m+n$ for any $u\sim v$ (let us assume $u\in A$ and $v\in B$) so from Cauchy's inequality \[\frac{n^2}{\deg u}+\frac{m^2}{\deg v}>m+n.\]Summing over all edges, we get the following contradiction: \[kmn(m+n)\leqslant e(m+n)<\sum_{\substack{u\sim v \\ u\in A \\ v\in B}}\left(\frac{n^2}{\deg u}+\frac{m^2}{\deg v}\right)=\sum_{u\in A}n^2+\sum_{v\in B}m^2=kmn(m+n).\]

A very instructive exercise in global summation, congratulations to dgrozev for proposing it and thanks for discussing with me an annoying flaw in my previous approach! I will leave to him to discuss origins and related ideas to this problem. Here goes the most natural approach. Evidently, $G$ has $km \cdot kn = k^2mn$ edges, so (thinking greedily) by Pigeonhole there is a collection of $e = kmn$ 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$, connected by an edge, with $\deg a + \deg b \geq m+n$, as then the component formed by $a$, $b$ and their neighbours would satisfy the requirements. To do that, we will again sum globally (i.e. throughout all edges) and rely on 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}{km} + \frac{(\sum_{b\in B} \deg b)^2}{kn}$. The sums in both numerators equal the number of edges (note that the graph is bipartite) which is $e = kmn$, so overall we have $\frac{e^2(m+n)}{kmn}$ as a lower bound. Now by Pigeonhole there is an edge $ab$ with sum of degrees at least $\frac{e(m+n)}{kmn} = m+n$, done!

This problem was proposed by me. Here is the official (my) solution. 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. \begin{align*} &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.\qquad (1) \end{align*}Then it holds $$\displaystyle \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, y'_i, i=1,2,\dots,\ell$. We can assume $x'_1\ge x'_2\ge \dots \ge x'_{\ell}.$ We shall prove that $y'_i$ are also in decreasing order. Let us assume on the contrary that $y'_i<y'_{i+1}$. Set $$\displaystyle x_i=x_{i+1}:=(x'_i+x'_{i+1})/2; y_i=y_{i+1}:=(y'_i+y'_{i+1})/2.$$Then (Chebyshev inequality) $$\displaystyle x_iy_i+ x_{i+1}y_{i+1}>x'_iy'_i+ x'_{i+1}y'_{i+1}.$$But it contradicts the maximality of $x'_i, y'_i, i=1,\dots,\ell$. Next, if $x'_1+y'_1<(x+y)/k$ we can similarly set $x_1:=x'_1+\varepsilon, x_2:=x'_2-\varepsilon; y_1:=y'_1+\delta, x_2:=x'_2-\delta$ for sufficiently small $\varepsilon, \delta\ge 0$ and get a larger value of $f.$ Therefore, $x'_1+y'_1=(x+y)/k.$ Let $k'$ be the largest index for which $x_{k'}>0$ and $y_{k'}>0.$ In the same way we can see that $x'_i+y'_i=(x+y)/k, i=1,2,\dots,k'.$ Hence, $k'\le k$. Assume that $k'<k$ and $y_i=0, i>k'.$ We modify $x',y'$ as follows. Set \begin{align*} \displaystyle x_i&:=x'_i, y_i:=y'_i, i=1,2,\dots,k'-1;\\ x_{k'}&:=x'_{k'}, y_{k'}:=y'_{k'}-\varepsilon, x_{k'+1}:=(x+y)/k, y_{k'+1}:=\varepsilon. \end{align*}For $i>k'+1$ we set $y_i=0$, and the values of $x_i, i>k'+1$ are irrelevant providing they comply with $(1)$. Since $x'_k<(x+y)/k$, it can be seen that $f(x,y)>f(x',y')$ which contradicts the maximality of $x',y'.$ Thus, $k'=k.$ We prove that $x'_i=x/k, y'_i=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\neq x/k$. WLOG let $x'_j <x/k.$ Then there exists $i>j$ for which $x'_i>x/k$. This means $x'_i>x'_j$ and thus the sequence $x'_1,x'_2,\dots,x'_k$ is not decreasing, contradiction. To recap, we established that $x'_i=x/k, y'_i=y/k, i=1,2,\dots,k.$ In this case $f(x',y')=kxy,$ and Lemma 1 is proved. $\square$ Back to the problem. The number of all edges of $K$ is $k^2mn$, 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'$, 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'$ 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 $$\displaystyle \sum{i=1}^{\ell} m_i=km,\sum_{i=1}^{\ell} n_i=kn, m_i+n_i<m+n.$$ According to Lemma 1, $$\displaystyle \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$. Remark. Three full solutions were presented. One was like in #2 (a bit artificial), one same as #3, and onе similar to this. More comments can be found in my blog.

We can generalize this problem. It boils down to prove that in a bipartite graph $G(A,B), |A|=km, |B|=kn$ with at least $kmn$ edges, there exists an edge $ e=ab, a\in A, b\in B$ such that $ \deg(a)+\deg(b)\ge m+n.$ Enumerate the vertices in $ A$ like $ a_1,a_2,\dots,a_{km}$ and the vertices in $ B$ - $ b_1,b_2,\dots,b_{kn}.$ We can represent this graph as an $ km\times kn$ table. In the cell $ (i,j)$ is written $ 1$ if there is an edge between $ a_i$ and $ b_j,$ otherwise we put $ 0$ there. To prove that there is an edge $ ab$ with $ \deg(a)+\deg(b)\ge m+n$ is equivalent to proving that there is a cell $ (i,j)$ such that $ a_{ij}=1$ and $$ \displaystyle \sum_{k=1}^n a_{ik} + \sum_{k=1}^m a_{kj}\ge m+n.$$Note that $$ \displaystyle \sum_{i=1}^{km}\sum_{j=1}^{kn}a_{ij}=kmn=\frac{km\cdot kn}{k}.$$Putting $ m$ in place of $ km$ and $ n$ in place of $ kn$ and calibrating the numbers by multiplying them by a constant, it boils down to prove the following claim. Claim 1. A $ m\times n$ table is given. Each cell $ (i,j)$ contains a number $ a_{ij}\in\{0,1\}.$ If $ \sum_{i,j} a_{ij}=S,$ then there exists a cell $ (i_0,j_o)$ with $ a_{i_0 j_0}=1$ such that $$ \displaystyle \sum_{k=1}^n a_{i_0k} + \sum_{k=1}^m a_{kj_0}\ge S\left(\frac{1}{m}+\frac{1}{n}\right).$$ Something stronger holds. Claim 2. A $ m\times n$ table is given. Each cell $ (i,j)$ contains a non-negative real number $ a_{ij}$ and $ \sum_{i,j} a_{ij}=S.$ Then there exists a cell $ (i_0,j_o)$ with $ a_{i_0 j_0}\neq 0$ such that $$ \displaystyle \sum_{k=1}^n a_{i_0k} + \sum_{k=1}^m a_{kj_0}\ge S\left(\frac{1}{m}+\frac{1}{n}\right).$$ Proof. It's enough to prove the claim in case $ S=1.$ We choose a cell $ (i,j)$ with probability $ p_{ij}:=a_{ij}.$ Denote by $ X$ the random variable $$ \displaystyle X= \sum_{k=1}^n a_{i_k} + \sum_{k=1}^m a_{kj}.$$Let's calculate the expectation of $ X.$ $$ \displaystyle \mathbb{E}[X]= \sum_{i,j}p_{ij}\left( \sum_{k=1}^n a_{i_k} + \sum_{k=1}^m a_{kj}\right)= \sum_{i,j}a_{ij}(R_i +C_j)$$where by $ R_i$ and $ C_i$ we denote the sum of the numbers in $ i$-th row, respectively $ j$-th column. Further calculation yields \begin{align*} \mathbb{E}[X]&= \sum_{i=1}^mR_i^2 + \sum_{j=1}^n C_j^2\\ &\ge \frac{1}{m}\left( \sum_{i=1}^m R_i \right)^2 + \frac{1}{n}\left( \sum_{j=1}^n C_j \right)^2\\ &=\frac{1}{m}+\frac{1}{n}. \end{align*}We used quadratic mean - arithmetic mean (QM-AM) inequality. Now, since $ \mathbb{E}[X]\ge \frac{1}{m}+\frac{1}{n},$ then $ X$ takes a value of at least $ \frac{1}{m}+\frac{1}{n},$ therefore there exists $ (i_0,j_0)$ with $ a_{i_0,j_0}>0$ and $ R_{i_0}+C_{j_0}\ge \frac{1}{m}+\frac{1}{n}.$ Pay attention that it is not possible $ a_{i_0j_0}=0$ because otherwise the probability of hitting $ (i_0, j_0)$ would be zero and we never choose such a cell. Remark. Claim 2 is not true for any real numbers. The condition that they are non-negative is essential. if we allow some of the numbers be negative. Some more comments on this can be found in my blog.