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

Question

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?

Thank you for your help

Answer 1

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

Answer 2

For completeness, here is a counterexample for $k=3$:

Consider the cycle $C_6$. Color alternate edges red and blue. Let $b^1$, $b^2$, and $b^3$ be the degree vectors for the 3 distinct matchings which consist of exactly 2 blue edges. Each vertex is incident to exactly 1 blue edge, and thus is included with degree 1 in exactly 2 of $\{b^1,b^2,b^3\}$, so these satisfy the total vertex degree condition.

However, observe each degree vector $b^i$ is uniquely satisfied by a matching on 2 blue edges; specifically no $b^i$-matching may include a red edge. Therefore we cannot decompose the graph.