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

1

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

graph

  • 0
    Ross Millikan: thank you, but why are you finding k? k is given, and can be anything. If k=8, m=4, n=8, then the lower bound is m-n+1, and not k.2011-05-23
  • 0
    Because you said there was (at least one) edge from each group that is part of U to a vertex of V. In your original post you thought the minimum was n-m+1 and this proves that is not correct. Do the groups have to be disjoint? Or just pairwise disjoint? I took them to be disjoint, but see you did not specify that. If a vertex can be part of more than one group, can an edge from it to V be counted by all of those groups, or only one?2011-05-23
  • 0
    The groups are not Disjoint sets, If it was not clear.. I agree that it can be min{k,n-m+1}. My main difficult is to prove the part of n-m+1.2011-05-23
  • 0
    Why would having more vertices in each group (increasing m) decrease the minimum number of edges? Is each vertex required to be in a group? In the above figure, I meant to show two groups of four, but you could also make it two overlapping groups of 72011-05-23
  • 0
    about your second question, it count by all groups which contain the vertex. meaning if the vetex "a" is in "group 1" and "gropu 2" then we know that "group 1" as at least one neighbor in V, and we know the same thing about "group 2". *but* it can't be that "a" will have a edge with vertex in "group 1" and also a edge with vertex in "group 2".2011-05-23
  • 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