that either (or both) of the following hold when $|A| = |B| > k$:
1) there are adjacent vertices $u \in A, v \in B$ both with degree > k or
2) there are non-adjacent vertices $u \in A, v \in B$ both with deg ≤.
Progress: I was thinking induction on . Suppose ∈ has deg()>. If one of its neighbors in has degree > k we're done. Otherwise all of them have degree ≤. Pick one of them ∈. Since deg()≤ there is at least one vertex in nonadjacent to . If it has degree ≤ then we're done. Otherwise all nonadjacent vertices will have degrees > k. The remove , and use induction...
Actually I'm not sure how to continue from here. Any help would be appreciated.
Let $$\begin{align} A'&=\{v\in A|\deg(v) >k\}\\ A''&=\{v\in A|\deg(v) \leq k\}\\ B'&=\{v\in B|\deg(v) >k\}\\ B''&=\{v\in B|\deg(v) \leq k\}\\ \end{align} $$ Unless each $v\in A''$ is adjacent to each $u\in B''$ and vice versa, we are done. If $A'=B'=\emptyset,$ so that $A=A'', B=B''$ then $|A''|=|B''|=n,$ say, so that $G=K_{n,n}$ and each vertex is of degree $n.$ By assumption, $n>k,$ so the theorem is true in this case.
Suppose $A'\neq\emptyset,$ and let $v\in A'.$ Is there is a $u\in B'$ adjacent to $v$ we are done, so assume all neighbors of $v$ are in $B''.$ By definition of $A',\ |B''|>k.$ Now there cannot be a vertex $w\in A''$ for it would be adjacent to each vertex in $B''$ and therefore have degree $>k,$ in contradiction of the definition of $A'',$ so $A''=\emptyset.$ Thus any vertex in $B'$ can only have neighbors in $A'$ so if $B'\neq\emptyset$ we are done. We have to deal with the situation where all vertices in $A$ have degree $>k$ and all vertices in $B$ have degree $\leq k,$ but this is impossible. Let $m$ be the number of edges in $G,$ and let $n=|A|=|B|.$ Then we have $$\sum_{v\in A}\deg(v)=m=\sum_{v\in B}\deg(v)$$ The first equality gives $m>nk$ and the second gives $m\leq nk.$
We get a similar contradiction if we assume $B'\neq\emptyset.$