# 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.

Title | maximal matching/minimal edge covering theorem |
---|---|

Canonical name | MaximalMatchingminimalEdgeCoveringTheorem |

Date of creation | 2013-03-22 12:40:05 |

Last modified on | 2013-03-22 12:40:05 |

Owner | mps (409) |

Last modified by | mps (409) |

Numerical id | 7 |

Author | mps (409) |

Entry type | Theorem |

Classification | msc 05C70 |

Related topic | MaximumFlowminimumCutTheorem |

Related topic | Matching |