5
$\begingroup$

I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings.

My main approach is to prove this inductively over the maximal degree d. This would require me to show that there must exist a matching which contains an edge for every one of the maximal degree nodes. (Such that the removal of this matching will leave me with a bipartite graph of maximal degree d, for which my inductive claim holds)

What I do know is to find a maximum matching (Via either some max-flow algorithm, or using the augmenting paths method, and arriving to the Gallai-Edmonds decomposition of the graph), but can't augment it to a maximum matching in which all maximal degree nodes are necessarily matched.

I was not able to prove it nor find a counter example for this subclaim, and would appreciate help. Thanks

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Possible approach: If a bipartite graph is $d$-regular then it can be decomposed into $d$ perfect matchings by Hall's theorem. Any bipartite graph of maximal degree $d$ can be completed to a $d$-regular bipartite graph (possibly by adding vertices).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I succeeded in proving the claim for d-regular graphs, but can't show the embedding is always possible so far. (Nor could I have shown that it can't be done in some specific instance) If you could expand on the way this embedding may be done, it would be helpful. $\endgroup$
    – user3661799
    Commented May 21, 2014 at 19:41
  • 2
    $\begingroup$ @user3661799 It's your exercise, but here is an idea. Take a complete $d$-regular bipartite graph, and remove an edge. You can now increase the degree of what vertex on each side of the original bipartite graph. $\endgroup$
    – Yuval Filmus
    Commented May 21, 2014 at 19:58
  • $\begingroup$ I am ashamed that I didn't see it immediately, thanks. $\endgroup$
    – user3661799
    Commented May 22, 2014 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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