Definition
Matching
A matching of an undirected graph
is a subset such that no two edges in share an endpoint. Example: The highlighted edge sets below show a matching
, a maximal matching , and a maximum matching .
Injectivity
Injective Endpoint Selection
Let
be a finite matching in , and let contain at least one endpoint of every edge in , i.e., is a vertex cover: Choosing one endpoint
for every defines an injective function Consequently,
.
Proof
Construct the endpoint-selection function
Every intersection
is non-empty, so choose one of its vertices and call it : This defines
. The condition 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
. Since is a matching, If their images were equal, the common image would belong to both edges:
contradicting
. Therefore, so
is injective. Compare cardinalities
By the pigeonhole principle, an injection from
to requires