# graphs – Min weighted edge cover: don’t follow proof in Schrijver

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})=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?