1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$).

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

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.