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?

  • $\begingroup$ Have you heard of the Hall's Marriage theorem? $\endgroup$ – Apple Mar 24 '15 at 13:36
  • $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.