Maximum Matching

Last updated Nov 1, 2022

Let $G$ be an Undirected Graph and let $\mathcal{M} = {M \subset E(G) : M \text{ is a Matching}}$. Then a Maximum Matching is a Matching $M \in \mathcal{M}$ so that $|M| = \max {|M| \leq |E(G)| : M \in \mathcal{M}}$.

1. Note this definition is Well-Defined even for Infinite Sets because Cardinals form a Well-Ordering.
2. The Set Cardinality of a Maximum Matching on $G$ is denoted $\nu(G)$.