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