I have tried for the last few days to prove that any bipartite graph of maximal

Question

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.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects