# Bipartite Graph Matching Proof

You have a bipartite graph where the vertices are partitioned into 10 boys and 20 girls. Every boy vertex has degree 6. Every girl vertex has degree 3. Show that there exists a matching that matches all the boys.

Isn't it obvious that there exists a matching which matches all the boys? The sum of degree of vertex of boys and girls are both 60. So there must be a a case where all boys are matched. But this isn't a good proof to give in a test in my opinion? I think there should be ways to prove this more firmly?

• It is, but YMMV, that is, it's highly probable that my "it's obvious" is for rather different reasons than yours. In particular "The sum of degree of vertex of boys and girls are both 60, so there must be a a case where all boys are matched." is wrong, that is true for all bipartite graphs and not all have side-saturating matchings. For example, take two copies of your graph with one side gender-switched (i.e. a graph of 30 boys and 30 girls). I suggest looking at the Hall's theorem. – dtldarek Nov 3 '14 at 10:46
• I have read about Hall's Theorem and simply using the theorem I can prove my question. But why do I even need to know how many girls are there. Let the boys be set B, |N(B)| is 60 and |B| is 10. According to Halls Theorem for any set A, as long as |N(A)| is greater or equal than |A|, a complete matching exists for set A. So I have already proved all boys will be matched without even the need to know how many girls are there. Isn't that a bit strange? – Benjamin Nov 3 '14 at 16:53
• Indeed you don't need to know how many girls there are, only that there are enough, which Hall's condition guarantees. However you are not 100% correct, note that it is: for any set $A$, if its every subset $W \subseteq A$ satisfies $|W| \leq |N(W)|$. If all subsets have enough neighbors, then $A$ can be matched. Any set of boys knowing enough girls is much stronger property than the one you mention. – dtldarek Nov 3 '14 at 17:25

## 1 Answer

Consider a bipartite graph with bipartition $(B,G)$, where $B$ represents the set of 10 boys and $G$ the set of 20 girls. Each vertex in $B$ has degree 6 and each vertex in $G$ has degree 3. Let $A \subseteq B$ be a set of $k$ boys. The number of edges incident to $A$ is $6k$. Since each vertex in $G$ has degree 3, the number of vertices in $G$ incident to the $6k$ edges is at least $6k/3 = 2k$. Thus, $A$ has at least $2k$ neighbors in $G$. Since $2k \ge k$, we have shown that every subset of $k$ vertices in $B$ has at least $k$ neighbors in $G$. Therefore Hall's condition is satisfied, and the graph has a complete matching from $B$ to $G$.

Regarding your comment that we do not need to know the number of girls, consider the following example. Suppose there are 10 boys and 6 girls, and suppose that all the boys are matched to all the girls. Then the sum of the degrees of the boy vertices is 60, which is larger than 10, but there is of course no complete matching from the boys to the girls. We need to ensure that the number of neighbors of $B$ (rather than the sum of the degrees of the vertices in $B$) is at least $|B|$. You can also construct examples where the number of boys and girls are equal in number, and the boys are matched to all the girls, but still there is no complete matching. For eg, consider the edge set $(b1, g1), (b1, g2), (b1, g3), (b2, g1), (b3, g1)$. Then, boy 1 is very popular, as is girl 1, but boys 2 and 3 can only be matched to girl 1, which means they both cannot be matched to different girls.

So this condition (on the number of neighbors) needs to be satisfied for each subset of $B$, not just the set $B$ itself.