# 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?

Here's a counter-example for $$k= 4$$.

Take $$G = K_{2,2}$$, specifically $$G=(V, E)$$ where $$V=\{1,2,3,4\}$$ and $$E=\{(1,3), (1, 4), (2,3), (2,4)\}$$.

Define $$b^1$$ by $$b^1_1 = b^1_3 = 1$$ and $$b^1_2=b^1_4=0$$. Define $$b^2 = b^1$$.

Define $$b^3$$ by $$b^1_1 = b^1_3 = 0$$ and $$b^1_2=b^1_4=1$$. Define $$b^4 = b^3$$.

Then there is just one $$b^1$$ matching (which is also the only $$b^2$$ matching), namely $$\{(1,3)\}$$.

Likewise there is just one $$b^3$$ matching (which is also the only $$b^4$$ matching), namely $$\{(2,4)\}$$.

But there is no way to decompose the graph into 4 parts, where the $$i$$th part is a $$b^i$$ matching. (Because, e.g., the first and second parts would both have to use the edge $$(1, 3)$$.)

The counter example extends directly to $$k\ge 4$$. I don't know about $$k=3$$.

• Aaaaaaarggggggh Aug 12, 2021 at 21:13