I was "inspired" to extend the concept of Maximum "$2$-to-$1$" matching in a bipartite graph 2-to-1 matching by extending it to "k-to-k" matching for some natural number k.

My strategy is as follows: Begin with $G = (L \dot \lor R, E)$ and find typical 1-1 matching here. Then, construct $G' = (L \dot \lor R, E')$ only with the edges that were not included in the matching from the previous step, and find the maximum matching for $G'$. Similarly, $G''$ will have only edges which were in neither of the maximum matchings from before. Repeat this procedure until $G^{(k-1)}$.

I cannot find a counter example to disprove this logic, but I am unable to prove it either.

My question is, is there something fundamental that I am missing here? Does this algorithm work?


1 Answer 1


Your procedure does not work. Consider the following graph:

enter image description here

This has a "$2$-to-$2$ matching". But if you start with the matching consisting of the vertical edges, the remaining graph does not have a perfect matching.

One the other hand, it is true that for some choices of perfect matchings, your method will return a $k$-to-$k$ matching, if there is one. This follows from (what I know as) Kőnig's theorem, which says that a $k$-regular bipartite graph can be decomposed into the union of $k$ perfect matchings.

By the way, the usual term for what you call a $k$-to-$k$ matching is a "$k$-factor".


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .