The definition of complete matching on p.129:
More generally, a complete matching from $V_1$ to $V_2$ in a bipartite graph $G(V_1, V_2)$ is a one-one correspondence between the vertices in $V_1$ and some of the vertices in $V_2$, such that corresponding vertices are joined.
Exercise 6.5 on p.133:
Prove that, if $G = G(V_1, V_2)$ is a bipartite graph in which the degree of each vertex in $V_1$ is not less than the degree of each vertex in $V_2$, then $G$ has a complete matching.
I cannot solve this problem.
My attempt is here:
Let $V_1 = \{v_{11}, v_{12}, \cdots v_{1m}\}$.
Let $\deg(v_{11}) \leq \deg(v_{12}) \leq \cdots \leq \deg(v_{1m})$.
Let $V_2 = \{v_{21}, v_{22}, \cdots v_{2n}\}$.
I think if $\deg(v_{1i}) = 0$ for some $i$, then $G$ has no complete matching.
So, we assume that $1 \leq \deg(v_{11})$.
We prove this exercise by induction on $m$.
If $m = 1$, then obviously $G$ has a complete matching.
$\cdots$
Thank you very much for your huge hints, bof.
We use the Hall's 'marriage' theorem:
Let $V_1 = \{v_{11}, v_{12}, \cdots v_{1m}\}$.
Let $1 \leq \deg(v_{11}) \leq \deg(v_{12}) \leq \cdots \leq \deg(v_{1m})$.
Let $V_2 = \{v_{21}, v_{22}, \cdots v_{2n}\}$.
Let $A = \{w_{11}, \cdots, w_{1k}\}$ be any non-empty subset of $V_1$.
Let $\phi(A) = \{w_{21}, \cdots, w_{2l}\}$.
Since any edge which is incident on a vertex in $A$ is also incident on a vertex in $\phi(A)$, so $$\deg(w_{11})+\cdots+\deg(w_{1k})\leq\deg(w_{21})+\cdots+\deg(w_{2l}).$$
And,
$$k \deg(v_{11}) \leq \deg(w_{11})+\cdots+\deg(w_{1k}).$$
And,
$$\deg(w_{21})+\cdots+\deg(w_{2l}) \leq l\deg(v_{11}).$$
So, $$k \deg(v_{11}) \leq \deg(w_{11})+\cdots+\deg(w_{1k})\leq\deg(w_{21})+\cdots+\deg(w_{2l})\leq l\deg(v_{11}).$$
So, $$k \leq l.$$
So, $$|A| \leq |\phi(A)|.$$