Theorem

Proof

Consider some edge $e \in M$ . At least one of the vertices that $e$ joins must be in $C$ , because $C$ is an edge covering and hence every edge is incident with some vertex in $C$ . Call this vertex $v_e$ , and let $f(e) = v_e$ .

Now we will show that $f$ one-to-one. Suppose we have two edges $e_1, e_2 \in M$ where $f(e_1) = f(e_2) = v$ . By the definition of $f$ , $e_1$ and $e_2$ must both be incident with $v$ . Since $M$ is a matching, however, no more than one edge in $M$ can be incident with any given vertex in $G$ . Therefore $e_1 = e_2$ , so $f$ is one-to-one.

Hence we now have that $|M| \leq |C|$ .

Corollary

Proof

Likewise, suppose $C$ is not a minimal edge covering. Then, by definition, there exists another covering $C'$ where $|C'| < |C|$ . But then $|C'| < |M|$ , which violates the above theorem.