Is the converse true?

Question

Let $G$ be a connected bipartite graph with partite sets $X$ and $Y$ such that cardinality of $X$ equals to cardinality of $Y$ $\geq$ 2. If every two vertices of $X$ have distinct degrees in $G$ then show that $G$ has a perfect matching. Is the converse true? Justify your answer.

Answer 1

We have to check that $G$ satisfies the conditions of Hall’s Marriage Theorem. Indeed, let $W$ be an arbitrary non-empty subset of $X$. Since all vertices of $W$ have distinct degrees (which are positive, because $G$ is connected), there exists a vertex $v\in W$ with degree $\deg v\ge |W|$. Then $|N_G(W)|\ge \deg v\ge |W|.$

The converse is not true. A simple example it a bipartite graph whose set of edges is a perfect matching.