I'm quite stuck on how to go about showing the second part of the following question:
Assume $G(V,E)$ is a bipartite graph with bipartition $V = P\cup Q$ and every vertex in $P$ has degree $a$, and every vertex in $Q$ has degree $b$. Show that $a|P| = b|Q|$. Show further that if $a \geq 1$, then $G$ has a maximal matching of size $min\{|P|, |Q|\}$.
I have shown that $a|P| = b|Q|$, but I am struggling with how to show the second part. I was thinking of trying to construct a new graph with source and sink nodes and using network flows, but got a bit confused with how to then show that the maximal flow is $min\{|P|, |Q|\}$.
Any help would be greatly appreciated.
Wlog assume $|P| \leqslant |Q|$ (and thus $a \geqslant b$).
Assume that for some $W \subseteq P$ we have $|W| > |N(W)|$. Then take subgraph on vertices $W \cup N(W)$ - every vertex on left part has degree $a$, thus the subgraph has $a \cdot |W|$ edges, but every vertex on right part has degree of at most $b$, thus subgraph has at most $b \cdot |N(W)| \leqslant a \cdot |N(W)| < a \cdot |W|$ edges.
This contradiction shows that for every $W \subseteq P$ we have $|W| \leqslant |N(W)|$. Then by Hall's marriage theorem there is $P$-saturating matching.