0
$\begingroup$

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.

  • 0
    If m=4, n=8, can't$k$be 2? Then if there is one edge from one vertex in each group of 4, there are only two edges in the graph. If you need to express it in n and m, it would be $\lceil \frac{n}{m} \rceil$2011-05-23

1 Answers 1

1

Following up on my comment, here is m=4, n=8, k=2:

graph

  • 0
    I thought the groups were part of U, so "a" can't have any edges with vertices in the groups. It can only have edges with vertices in V. It looks to me like you need to specify the problem more carefully.2011-05-23