Expanding Hall's theorem [closed]

Question

I'm trying to get a "feel" about Hall's theorem and try to expand it for one to many matching. So my question is:

Given a bipartite graph, what would be 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.

Iv'e "cloned" the vertices on the "one side", and for each edge from v to u where v is on the "one side" and u is on the other side, Iv'e connected an additional edge between v_clone and u. I'm trying to figure out what would be the condition(s)? when I return to my original graph. And how can I prove it? Thanks!

Answer 1

Let $G$ be a bipartite graph with bipartition $(L,R)$. A necessary and sufficient condition for each vertex on the left to be matched to two vertices on the right is $|N_G(X)| \geq 2|X|$ for all $X \subseteq L$, This can be proved by applying Hall's theorem to the auxiliary graph that you defined.

There are many related results. For example, $G$ contains a forest $F$ such that $\deg_F(v)=2$ for all $v \in L$ if and only if $|N_G(X)| > |X|$ for all non-empty $X \subseteq L$. This is an old result of Lovász. There is also a $(2-\epsilon)$ version of Hall's theorem for the existence of VW-matchings (these are subgraphs where every connected component looks like a V or a W), due to Bennett, Bonacina, Galesi, Molloy, Wollan, and myself. Finally, see this paper of Roberts for a very general result about 'tree matchings', which implies both Lovász's theorem and the result on VW-matchings.