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
    As I read it, you could have one vertex in $V$ which connects to all the required vertices in $U$. Did you mean to say that each of the $m$ has a different neighbor in $V$? Even so, it seems $m$ would be enough.2011-05-23
  • 0
    @Ross Millikan: you right. sorry for that. I edited the question.2011-05-23
  • 0
    Even with the edit, it seems $k$ (not $m$ as in my previous comment) is enought. If only one vertex in the group is connected to a vertex in $V$, and all those vertices are distinct, there are only $k$ connections.2011-05-23
  • 0
    @Ross Millikan: Thank you, but why k? for example in group U, when m=4 and n=8 there are a lot of groups (which marked as k). but the lower bound is 5. second, I need to find it my n and m, and not by k. my main problem is to prove it.2011-05-23
  • 0
    I'm having a hard time following you, Amir. Do you see how what you've listed as "forbidden" leads to Ross's comment?2011-05-23
  • 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