I have a question about how to prove part of a bigger proof.
I have Bipartite graph (with two groups: $U$ and $V$ with $n$ vertices each). In $U$, I have $k$ groups, each one of the contains $m < n$ vertices. For each group there is at least one neighbor in $V$.
I want to find the lower bound of pairs :$(u,v)| u$ contained in $U$ and $v$ contains in $V$.
Note: The case ($u_i$,$v_j$) ($u_t$,$v_j$) is forbidden, meaning: for each $u_i$, there is a different $v$ connected to $u_i$, not already connected to a $u_j$ where $i\neq j$. (edited)
I think that this bound is: $n-m+1$. But I don't know how to prove it. The reason for this bound is the fact that for each group in $U$, I can look on another group in $U$, which doesn't contain the different vertices in the previous group. This group also has one neighbor in $V$, and so on.
But what do I do when I have more that one neighbor in the group? On which group am I looking?
I've tried induction, but my efforts didn't work.
Thank you for your help.