Forcing bipartite graphs? Show that deleting at most (m-s)(n-t)/s edges from a K_{m,n} will never destroy all its K_{s,t} subgraphs. I'm completly stuck here and any help would be welcome!
 A: Here is a hint:  If you can find some number $N$ of edge-disjoint $K_{s,t}$ subgraphs of $K_{m,n}$, then because they are edge-disjoint, you would have to delete at least $N$ edges from $K_{m,n}$ to be sure none of your subgraphs was intact.
A: Firstly, I'll assume $m \geq s \geq 1$ and $n \geq t \geq 1$, otherwise the claim is boring (or false).  We can further assume $m>s$, otherwise the claim is trivial.
Notation: We can find $\lfloor m/s \rfloor$ disjoint $s$-subsets $S_1,S_2,\ldots,S_{\lfloor m/s \rfloor}$ of the vertices belonging to the part of size $m$.  Let the vertices belonging to the part of size $n$ be labelled $1,2,\ldots,n$.
Algorithm
We will analyse the following algorithm for finding a $K_{s,t}$ subgraph:


*

*Input: any subgraph $G$ of $K_{m,n}$.  Let $D$ be the set of edges deleted from $K_{m,n}$ to form $G$.

*For $i \in \{1,2,\ldots,\lfloor m/s \rfloor\}$ do:


*

*Set $T=\{1,2,\ldots,t\}$.

*While (true) do:


*

*If $S_i \cup T$ induces a $K_{s,t}$ in $G$ then we are done (return $S_i \cup T$).

*Otherwise there exists an edge $e_\mathrm{left}e_\mathrm{right} \in D$ with $e_\mathrm{left} \in S_i$ and $e_\mathrm{right} \in T$.  Delete $e_\mathrm{right}$ from $T$.

*If $\mathrm{max}(T)+1 \leq n$ then add $\mathrm{max}(T)+1$ to $T$.  Otherwise break (out of the while loop).



*return fail.
Analysis
Assume a $K_{s,t}$ is not found (i.e., fail is returned).  For any $i$, the while loop will be executed exactly $n-t+1$ times (since $\max(T)$ increases by $1$ in each iteration).  The for loop will be executed exactly $\lfloor m/s \rfloor$ times.  Thus, in total, the while loop is executed $\lfloor m/s \rfloor(n-t+1)$ times.  In each execution of the while loop, a distinct deleted edge is identified.  Thus, at least $$\lfloor m/s \rfloor(n-t+1)$$ edges must have been deleted from $K_{m,n}$.  This implies the claim in the question.

Note that aaron's earlier suggested approach does not work in general; a counterexample is when $m=n=7$ and $s=1$ and $t=4$.  There are $7^2=49$ edges in $K_{7,7}$ and therefore there can be at most $\lfloor 49/4 \rfloor=12$ edge-disjoint copies of $K_{1,4}$ in $K_{7,7}$.  However, the question allows us to delete $(m-s)(n-t)/s=18$ edges, which is more than enough to destroy $\leq 12$ edge-disjoint copies of $K_{1,4}$.
