One to many matching, using Hall's theorem?

Question

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!

Answer 1

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.

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$.

Answer 2

Neccessary condition:

Let $G=\{V_1 \cup V_2, E\}$ be a bipartite graph where $V_1$ and $V_2$ are his sides. It is given that for any $v$ element of $V_1$ we can match $2$ neighbours from $V_2$ that are only his. Thus for any $A$ subset of $V_1$, $|N_G(A)| \geq 2|A|$.

Sufficient condition:

We assume that for any $A$ subset of $V_1$, $|N_G(A)| \geq 2|A|$. We do the following construction of $G'=\{V_1' \cup V_2, E'\}$ where $V_1'= V_1 \cup V_1''$ and $E'= E \cup E''$:

1. for each vertex $v$ in $V_1$ we clone a vertex $v''$ that is an element of $V_1''$.
2. for any edge $\{v,u\}$ where $v$ is in $V_1$ and $u$ is in $V_2$, we connect an edge $\{v'',u\}$ that is an element of $E''$ where $v''$ is in $V_1''$ and $u$ is in $V_2$.

Now, because we cloned vertices in side $V_1$ and for any new cloned vertex we connected an edge from it to all of its origin's neighbours, and from our first assumption we get that for any $A$ subset of $V_1'$: $|N_G(A)| \geq |A|$. That means that our $G'$ satisfies Hall's condition; thus it has a matching that covers $V_1'$. Now in $V_1'$ any vertex is represented twice, and therefore you can match for each $v$ of $V_1$ two neighbours that are only his from $V_2$.