Let $G$ be a connected $U-W$ bipartite graph (i.e., a connected bipartite graph with parts $U$ and $W$). Assume that the cardinalities of $U$ and of $W$ are equal and $\geq 2$. Assume also that the degrees of the vertices in $U$ are all different.
Prove that $G$ contains a perfect matching.
Could anyone help me this question?
First, note that the connectivity of $G$ ensures that the degree of every vertex is at least $1$.
For any set of vertices $S\subseteq U$, the degrees of the vertices in $S$ are all different positive integers, and all at least $1$. It follows that $\displaystyle\max_{u\in S}\{\deg(u)\}\ge |S|$ for every $S\subseteq U$, and this is sufficient to ensure the conditions of Hall's marriage theorem are satisfied. It follows that there indeed exists a perfect matching as desired.