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