How would we prove that the following bipartite graph has a perfect matching?

Question

Let G be a bipartite graph with bipartition (A, B), satisfying ∣A∣ = ∣B∣. Suppose that G is connected and that every vertex in B has a different degree. Prove that G contains a perfect matching.

So I understand the whole idea that for a graph to be bipartite, it must have every edge going from one side to another. And I understand that for the graph to have a perfect matching, it must have every vertex belonging to an edge.

But is there a proper way to prove that this particular one does. If so, what would that method be?

Answer 1

Let $n=|A|=|B|$. Show that the vertices in $B$ have degrees $1,2,\ldots,n$. Show then that Hall's conditions are satisfied (each $r$ vertices from $B$ have at least $r$ neighbours in $A$).

Answer 2

Hint:

• Consider the following algorithm:
  1. Let $\{b_1, b_2, \ldots \}$ be the vertices of $B$ sorted ascending by their degree.
  2. In the above order take $v_i$ and if it has unmatched neihbors, match it to any of them.
• Let $d_1, d_2, \ldots$ be the sequence of degrees of $v_i$'s, in particular, $d_1 \geq 1$ (because the graph is connected) and it grows each turn at least by one (because $d_i$'s are all different).
• Let $m_1, m_2, \ldots$ count the previously matched pairs, in particular, $m_1=0$ (because we had no matched pairs prior to turn zero) and the sequence grows each turn at most by one (because we can match at most one pair per turn).
• Observe that $m_i < d_i$.

I hope this helps $\ddot\smile$