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$ 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$ Commented May 21, 2014 at 19:58
  • $\begingroup$ I am ashamed that I didn't see it immediately, thanks. $\endgroup$ Commented May 22, 2014 at 6:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.