One to many matching, using Hall's theorem?
I'm having a difficult time finding the neccessary and sufficient condition in the question and would love some help, I thought I had it but found a counter example for my "proof". The question is:
Given a bipartite graph, find a neccessary and sufficient condition for that it would be possible to match every vertex on one side, to two vertices on the other side, that would belong only to him.
Thanks!
$\endgroup$ 52 Answers
$\begingroup$Given the bipartite graph $ U \times V$, it would be possible to match every vertex on one side, to two vertices on the other side, if and only if
Given the bipartite graph $ ( U + U') \times V$ (where the edges of $U' \times V$ are exactly what you think) ...
$ $
has a perfect matching.
Now convert this back to $ U \times V$.
$ $
Hint: It has a very similar flavor to Hall Marriage Theorem. You should be able to guess what the (obvious) change is.
$\endgroup$ 12 $\begingroup$Given any $ u$ vertices in $U$, the image in $V$ has size $ \geq 2u$.
Given any $2v$ vertices in $V$, the image in $U$ has size $ \geq v$.
Neccessary condtion: Let G={V1 U V2, E} be a bipartite graph where V1 and V2 are his sides. It is given that for any v element of V1 we can match 2 neighbours from V2 that are only his. Thus for any A subset of V1 |NG(A)|>=2*|A|.
Sufficient condition: We assume that for any A subset of V1 |NG(A)|>=2*|A|. we do the following construction of G'={V1' U V2, E'} where V1'= V1 U V1'' and E'= E U E'': 1) for each vertex v in V1 we clone a vertex v' that is an element of V1''. 2) for any edge {v,u} where v is in V1 and u is in V2, we connect an edge {v'',u} that is an element of E'' where v'' is in V1'' and u is in V2.
now, because we cloned vertices in side V1 and for any new cloned vertex we connected an edge from it to all of its origins neighbours, and from our first assumption we get that for any A subset of V1': |NG(A)|>=|A|. that means that our G' satisfies Hall's condition, thus it has a matching that covers V1'. now in V1' any graph is represented twice, and therefore you can match for each v of V1 two neighbours that are only his from V2.
$\endgroup$ 2
