bipartite graph has a matching such that all vertices on one side are matched.

Question

Let $G$ be a bipartite graph with partition sets $V_1,V_2$. Suppose for any edge $v_1v_2$ with $v_i \in V_i$ for $i=1,2$, we have $d(v_1) \ge d(v_2)$. Show that $G$ has a matching such that all vertices in $V_1$ are matched.

Answer 1

Give each edge $v_1v_2; v_1 \in V_1, v_2 \in V_2$ a weight of $d^{-1}(v_1)$ and call the resulting weighted graph $H$. Then every vertex in $V_1$ has weighted degree exactly 1 in $H$ and every vertex in $V_2$ has weighted degree no larger than 1 [make sure you see why].

Furthermore $U$ be any subset of $V_1$ and let $N(U)$ be the set of vertices in $V_2$ adjacent in $H$ to at least one vertex in $U$. Now let $H[U \cup N(U)]$ be the induced subgraph of $H$ on $U \cup N(U)$. Then every vertex $v_1$ in $U$ has degree $d'(v_1)$ exactly 1 in $H[U \cup N(U)]$ while every vertex $v_2$ in $N(U)$ has degree $d'(v_2)$ no larger than 1 in $H[U \cup N(U)]$ . However, also note the equation $\sum_{v_1 \in U} d'(v_1) = \sum_{v_2 \in N(U)} d'(v_2)$ [make sure you see why]. Conclude that $|N(U)|$ must be at least as large as $|U|$. However, iff $v_1$ and $v_2$ are adjacent in $H$ then they are adjacent in $G$, so the number of vertices in $V_2$ adjacent in $G$ to at least one vertex in $U$ is $|N(U)| \ge |U|$. So finish using Hall's Matching Theorem.