# Partition the edges of a bipartite graph into perfect $b$-matchings

Any $$r$$-regular bipartite graph can be partitioned into $$r$$ disjoint perfect matchings. I want to know whether a version of this extends to perfect $$b$$-matchings.

Suppose we have a bipartite graph $$G = (V,E)$$. Given a vector $$b \in \mathbb{Z}^V$$, a perfect $$b$$-matching is an edge-subgraph $$E'$$ such that each vertex $$v$$ in $$(V,E')$$ has degree exactly $$b_v$$.

Now I have a bipartite graph and a collection of vectors $$b^1, \ldots, b^k$$. I am guaranteed that for each $$b^i$$, there exists a perfect $$b^i$$ matching in my graph, and that $$deg(v) = \sum_{i=1}^k b^i_v$$ for all $$v$$.

Question: Can I partition the edges of my bipartite graph into $$k$$ parts, where for each $$i$$, the i'th part is a perfect $$b^i$$-matching?

Attempt: I have proved this for $$k=2$$. Indeed, I can immediately remove the guaranteed $$b_1$$ matching, and because of the degree condition, the remaining edges will form a perfect $$b_2$$-matching.

However, the cases for $$k \geq 3$$ is unclear to me.... I suspect it is false. Does anyone know one way or the other?

Take $$K_{2,2}$$ with vertices in one part $$\{x_1,x_2\}$$ and the other $$\{y_1,y_2\}$$. Let $$b^i(x_i) = b^i(y_i) = 1$$ and $$b^i(x_{3-i}) = b^i(y_{3-i}) = 0$$ for $$i=1,2$$. Let $$b^3 = b^1$$ and $$b^4 = b^2$$. Then $$b^1, b^2, b^3, b^4$$ satisfy the requirements (there exists $$b^i$$-matchings for each $$i$$ and they sum to the degrees), but $$b^1$$ and $$b^3$$ matchings are never disjoint.
• The $b^i$ vectors are supposed to have an entry for every vertex in the graph, but it seems like you have only specified the values on the $a_i$. Aug 11, 2021 at 16:29