# bipartite graph has perfect matching

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?

• Have you heard of the Hall's Marriage theorem? – Apple Mar 24 '15 at 13:36
• @Apple Yes, I know this theorem, but I am confused how to use the condition that the degrees of the vertices in U are all different. I don't know how to relate this condition to marriage thm. – ZHJ Mar 24 '15 at 13:47

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.