Let $G = (L, R, E)$ be a complete bipartite graph, where $L$ and $R$ are disjoint sets of vertices. Let $|L| = n, |R|=m$, where $n < m$. The algorithm consists of several iterations and in each iteration we do the following: we consider any matching that covers all vertices from $L$ and delete all the edges from this matching. Note that at some moment there will be no matchings in the graph that covers $L$. This means that the algorithm should be terminated. What is the maximum number of iterations with such deleting can we make for sure before termination of the algorithm?
Using Hall's marriage theorem I managed to find that we can guarantee $m-n$ iterations. I also know that for $n = m$ we can guarantee $n$ iterations. So now I want to prove that in any case we can guarantee $n$ iterations. Is it true? Any ideas about that?
Any help would be greatly appreciated. Thanks in advance.