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
Best Answer
It is false.
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.