Bipartite graph with weight function such that the sum of weight of neighbours is 1

Question

Suppose $G=(A,B)$ is a bipartite graph with bipartition $(A,B)$ with weight function $w: E(G)\rightarrow \mathbb{R}_{\geq 0}$. Suppose $G$ has the property that for any vertex $v$, $\sum_{u \in N(v)}w(uv)=1$. We can prove that $G$ must have a perfect matching. But I also want to prove the following, there exists perfect matchings, $M_1,...,M_k$ and non-negative numbers $c_1,...,c_k$ such that for every $e \in E(G)$, $\sum_{i: e\in M_i}c_i = w(e)$ and further $\sum_{i=1}^{k}c_i=1$

Answer 1

Note that if there is some constant $C > 0$ such that for every vertex $v$, $\sum_{u \in N(v)}w(uv) = C$, then there is a perfect matching in $G$, since after multiplying the weights by $1/C$, we're back to the $C = 1$ case.

This observation allows us to solve the problem greedily. Take a perfect matching $M_1$ in $G$ and let $c_1$ be $\min\{w(e) : e \in M\}$. Now we update the graph by decreasing the weight of the edges in $M_1$ by $c_1$ and removing the edges from $G$ whose weight have become zero.

Since $M$ was a perfect matching, in this new graph we have that for every vertex $v$, $\sum_{u \in N(v)}w(uv) = 1 - c_1$. Now we can iterate the above to get another perfect matching $M_2$, and so on. Note that in each iteration we delete at least one edge of $G$, so in a finite number of steps we reach a state where $G$ has no more edges, or equivalently, where every edge of the original graph has zero weight. Since at the end of each iteration $\sum_{u \in N(v)}w(uv) = 1 - (c_1 + \dots + c_k) = C$ was constant for all $v$, this must mean that $C = 0$, so that $\sum c_i = 1$. Also, the final weight $w'(e)$ of an edge is just $w(e) - \sum_{i: e \in M_i}c_i$. Since $w'(e) = 0$, this gives $w(e) = \sum_{i: e \in M_i}c_i$, as desired.