maximal matching/minimal edge covering theorem

Theorem

Let $G$ be a graph. If $M$ is a matching on $G$, and $C$ is an edge covering for $G$, then $|M|\le |C|$.

Proof

Consider an arbitrary matching $M$ on $G$ and an arbitrary edge covering $C$ on $G$. We will attempt to construct a one-to-one function $f:M\to C$.

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|\le |C|$.

Corollary

Let $G$ be a graph. Let $M$ and $C$ be a matching and an edge covering on $G$, respectively. If $|M|=|C|$, then $M$ is a maximal matching and $C$ is a minimal edge covering.

Proof

Suppose $M$ is not a maximal matching. Then, by definition, there exists another matching $M^{\prime }$ where . But then $|M^{\prime }|>|C|$, which violates the above theorem.

Likewise, suppose $C$ is not a minimal edge covering. Then, by definition, there exists another covering $C^{\prime }$ where . But then , which violates the above theorem.