I’m reading section 19.3 of Combinatorial Optimization by Schrijver where he details an algorithm for finding the min-weight edge cover. His method works for general graphs, but I’m particularly interested in bi-partite graphs. To find the min-weighted edge cover of a graph $G=(V,E)$ with a weight function $w: E to R$, he first defines a clone graph, $tilde{G} = (tilde{V},tilde{E})$. He then defines a larger graph, $G’=(V’,E’)$ whose set of vertices, $V’$ is the union of $V$ and $tilde{V}$. The edges, $E’$ and weight function $w'(E’)$ are as follows:

- $w'(e)=w'(tilde{e})=w(e)$ for $e in E$
- $w'(v,tilde{v})=2mu(v)$ for each $v in V$ where $mu(v)$ is the minimum weight edge of $G$ incident on $v$.

Now, we construct a minimum weight perfect matching, $M$ for $G’$ and this yields a minimum weight edge cover $F$ for $G$ once we replace any edge $vtilde{v}$ in $M$ by an edge $e_v$ of minimum weight of $G$ incident on $v$.

Now, for the proof that this works, the author notes that $w(F)=frac{1}{2}w'(M)$. So far so good.

Then, he states that any edge cover $F’$ for $G$ gives by reverse construction a perfect matching $M’$ in $G’$ with $w'(M’)leq 2w(F’)$.

This is the part I don’t understand. How does one go about constructing this new perfect matching, $M’$ and further prove the inequality?