Min weighted edge cover: don't follow proof in Schrijver

Question

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:

1. $w'(e)=w'(\tilde{e})=w(e)$ for $e \in E$
2. $w'(v,\tilde{v})=2\mu(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 $v\tilde{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?

Answer 1

Let $M$ be a maximal subset of $F'$ which is a matching. Any vertex $v$ not covered by $M$ must be covered by some edge $e_v=(v,w)$ in $F'$. Since $M$ is maximal, $w$ must be covered by $M$. It follows that if $v_1 \neq v_2$ are not covered by $M$, then $e_{v_1} \neq e_{v_2}$.

The matching $M'$ consists of the two copies of each edge in $M$, and of the edges $(v,\tilde{v})$ for each $v$ not covered by $M$. Edges of the first type have total weight $2w(M)$. Since $w(v,\tilde{v}) \leq 2w(e_v)$, edges of the second type have total weight at most $2w(F' \setminus M)$ (this crucially uses that $e_{v_1} \neq e_{v_2}$ for any $v_1 \neq v_2$ not covered by $M$). Hence $w(M') \leq 2w(F')$.