Show that if G(U, W) is a bipartite graph such that min u∈U degree(u) ≥ max w∈W degree(w), then G has a matching of size |U|.

Question

I'm assuming that for this question |U| $\le$ |W| is implied.

I can intuitively see why this is true; as the degree of each vertex of U is greater or equal to any vertex of W then at worst there exists |U| edges, each between a unique pair $(v_u, v_w)$ for all $v_u$ in U, and hence a matching of size |U| exists, but I'm not sure this is a satisfactory proof.

Does anything need to be added to/reworded in this?

Thanks!

Answer 1

Hint:

• Hall's theorem.
• Suppose that there exists set $U'\subseteq U$ such that $|U'|>|\mathcal{N}(U')|$, then the average degree in $U'$ is smaller than the average degree in $\mathcal{N}(U')$.

I hope this helps $\ddot\smile$