<p>Here's a counter-example for <span class="math-container">$k= 4$</span>.</p>
<p>Take <span class="math-container">$G = K_{2,2}$</span>, specifically <span class="math-container">$G=(V, E)$</span> where <span class="math-container">$V=\{1,2,3,4\}$</span> and <span class="math-container">$E=\{(1,3), (1, 4), (2,3), (2,4)\}$</span>.</p>
<p>Define <span class="math-container">$b^1$</span> by <span class="math-container">$b^1_1 = b^1_3 = 1$</span> and <span class="math-container">$b^1_2=b^1_4=0$</span>.
Define <span class="math-container">$b^2 = b^1$</span>.</p>
<p>Define <span class="math-container">$b^3$</span> by <span class="math-container">$b^1_1 = b^1_3 = 0$</span> and <span class="math-container">$b^1_2=b^1_4=1$</span>.
Define <span class="math-container">$b^4 = b^3$</span>.</p>
<p>Then there is just one <span class="math-container">$b^1$</span> matching (which is also the only <span class="math-container">$b^2$</span> matching), namely <span class="math-container">$\{(1,3)\}$</span>.</p>
<p>Likewise there is just one <span class="math-container">$b^3$</span> matching (which is also the only <span class="math-container">$b^4$</span> matching), namely <span class="math-container">$\{(2,4)\}$</span>.</p>
<p>But there is no way to decompose the graph into 4 parts, where the <span class="math-container">$i$</span>th part is a <span class="math-container">$b^i$</span> matching.  (Because, e.g., the first and second parts would both have to use the edge <span class="math-container">$(1, 3)$</span>.)</p>
<p>The counter example extends directly to <span class="math-container">$k\ge 4$</span>.  I don't know about <span class="math-container">$k=3$</span>.</p>

CC BY-SA 4.0
2021-08-12T21:13:45.403Z
Aaaaaaarggggggh
Karagounis Z
CC BY-SA 4.0
2021-08-12T18:26:45.097Z
2021-08-12T18:26:45.097Z
Neal Young
<p>For completeness, here is a counterexample for <span class="math-container">$k=3$</span>:</p>
<p>Consider the cycle <span class="math-container">$C_6$</span>. Color alternate edges red and blue. Let <span class="math-container">$b^1$</span>, <span class="math-container">$b^2$</span>, and <span class="math-container">$b^3$</span> 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 <span class="math-container">$\{b^1,b^2,b^3\}$</span>, so these satisfy the total vertex degree condition.</p>
<p>However, observe each degree vector <span class="math-container">$b^i$</span> is uniquely satisfied by a matching on 2 blue edges; specifically no <span class="math-container">$b^i$</span>-matching may include a red edge. Therefore we cannot decompose the graph.</p>

CC BY-SA 4.0
2024-09-14T18:28:39.223Z
2024-09-21T21:32:08.197Z
2024-09-21T21:32:08.197Z
Tommy
<p>Any <span class="math-container">$r$</span>-regular bipartite graph can be partitioned into <span class="math-container">$r$</span> disjoint perfect matchings.
I want to know whether a version of this extends to perfect <span class="math-container">$b$</span>-matchings.</p>
<p>Suppose we have a bipartite graph <span class="math-container">$G = (V,E)$</span>. Given a vector <span class="math-container">$b \in \mathbb{Z}^V$</span>, a perfect <span class="math-container">$b$</span>-matching is an edge-subgraph <span class="math-container">$E'$</span> such that each vertex <span class="math-container">$v$</span> in <span class="math-container">$(V,E')$</span> has degree exactly <span class="math-container">$b_v$</span>.</p>
<p>Now I have a bipartite graph and a collection of vectors <span class="math-container">$b^1, \ldots, b^k$</span>. I am guaranteed that for each <span class="math-container">$b^i$</span>, there exists a perfect <span class="math-container">$b^i$</span> matching in my graph, and that <span class="math-container">$deg(v) = \sum_{i=1}^k b^i_v$</span> for all <span class="math-container">$v$</span>.</p>
<p><strong>Question:</strong> Can I partition the edges of my bipartite graph into <span class="math-container">$k$</span> parts, where for each <span class="math-container">$i$</span>, the i'th part is a perfect <span class="math-container">$b^i$</span>-matching?</p>
<p><strong>Attempt:</strong> I have proved this for <span class="math-container">$k=2$</span>. Indeed, I can immediately remove the guaranteed <span class="math-container">$b_1$</span> matching, and because of the degree condition, the remaining edges will form a perfect <span class="math-container">$b_2$</span>-matching.</p>
<p>However, the cases for <span class="math-container">$k \geq 3$</span> is unclear to me.... I suspect it is false. Does anyone know one way or the other?</p>
<p>Thank you for your help</p>

CC BY-SA 4.0
2024-09-23T10:15:24.687Z
This question is also on math.SE: https://math.stackexchange.com/questions/4222259/partition-the-edges-of-a-bipartite-graph-into-perfect-b-matchings
Antoine Amarilli 'a3nm'
<graph-theory><graph-algorithms><co.combinatorics><optimization><bipartite-graphs>
Partition the edges of a bipartite graph into perfect $b$-matchings
Karagounis Z
# Partition the edges of a bipartite graph into perfect $b$-matchings

(Asked by: username_0 on 2021-08-10)

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

**Tags:** graph-theory, graph-algorithms, co.combinatorics, optimization, bipartite-graphs

> **Comments:**
> **username_1**: This question is also on math.SE: https://math.stackexchange.com/questions/4222259/partition-the-edges-of-a-bipartite-graph-into-perfect-b-matchings  

---

## 2 answers

### Answer by username_2 on 2021-08-12. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: Aaaaaaarggggggh  

---

### Answer by username_3 on 2024-09-14. Score: 0

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.


---

