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?
 A: 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. 
