0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's a good exercise, but for Math.SE content purposes, having some context to indicate how you are thinking about it will be an improvement. $\endgroup$ – hardmath Sep 17 '18 at 18:24
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.