Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

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$.


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.


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}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.