Matching

Definition

Matching

A matching of an undirected graph $G=(V,E)$ is a subset $M\subseteq E$ such that no two edges in $M$ share an endpoint.

Example: The highlighted edge sets below show a matching $M_1$, a maximal matching $M_2$, and a maximum matching $M_3$.

Injectivity

Injective Endpoint Selection

Let $M$ be a finite matching in $G=(V,E)$, and let $S\subseteq V$ contain at least one endpoint of every edge in $M$, i.e., $S$ is a vertex cover:

$$\forall e\in M:e\cap S\ne \varnothing .$$

Choosing one endpoint $f(e)\in e\cap S$ for every $e\in M$ defines an injective function

$$f:M\hookrightarrow S.$$

Consequently, $|M|\le |S|$.

Proof

Construct the endpoint-selection function

Every intersection $e\cap S$ is non-empty, so choose one of its vertices and call it $f(e)$:

$$\forall e\in M:f(e)\in e\cap S.$$

This defines $f:M\to S$. The condition $f(e)\in e$ records that the chosen vertex is an endpoint of the edge; without it, disjointness of the edges would give no information about their images.

Distinct edges receive distinct endpoints

Take distinct $e,e^{\prime }\in M$. Since $M$ is a matching,

$$e\ne e^{\prime }⟹e\cap e^{\prime }=\varnothing .$$

If their images were equal, the common image would belong to both edges:

$$\begin{array}{rl}f(e)=f(e^{\prime })& ⟹f(e)\in e\cap e^{\prime }\\ & ⟹e\cap e^{\prime }\ne \varnothing ,\end{array}$$

contradicting $e\cap e^{\prime }=\varnothing$. Therefore,

$$e\ne e^{\prime }⟹f(e)\ne f(e^{\prime }),$$

so $f$ is injective.

Compare cardinalities

By the pigeonhole principle, an injection from $M$ to $S$ requires

$$\underset{\text{distinct endpoint per edge}}{\underbrace{f:M\hookrightarrow S}}⟹|M|\le |S|.$$