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

## 1 Answer

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