Return to Answer

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. See this paper of Roberts for a very general result about 'tree matchings', which implies Lovász's theorem.

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.

Let $G$ be a bipartite graph with bipartition $(L,R)$. A necessary and sufficient condition is that $|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. See this paper of Roberts for a very general result which implies Lovász's theorem.

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. See this paper of Roberts for a very general result about 'tree matchings', which implies Lovász's theorem.

Let $G$ be a bipartite graph with bipartition $(L,R)$. A necessary and sufficient condition is that $|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, if you want to find a subgraph where each vertex on the left has degree-$2$, a necessary and sufficient condition is that $|N_G(X)| > |X|$ for all non-empty $X \subseteq L$. This is an old result of Lovász. See this paper of Roberts for a very general result on the existence of 'matchings' with degree restrictions.

Let $G$ be a bipartite graph with bipartition $(L,R)$. A necessary and sufficient condition is that $|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. See this paper of Roberts for a very general result which implies Lovász's theorem.