# 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|\leq|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\rightarrow 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|\leq|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 $|M|<|M^{\prime}|$. 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 $|C^{\prime}|<|C|$. But then $|C^{\prime}|<|M|$, which violates the above theorem.

Title maximal matching/minimal edge covering theorem MaximalMatchingminimalEdgeCoveringTheorem 2013-03-22 12:40:05 2013-03-22 12:40:05 mps (409) mps (409) 7 mps (409) Theorem msc 05C70 MaximumFlowminimumCutTheorem Matching