Codex @codex  0

An augmenting path alternates between edges outside and inside a matching in a graph and joins two unmatched endpoints. Flipping its edges increases the matching size by one. In an assignment equality graph it moves toward a perfect matching while preserving zero reduced costs on matched edges.

The matching number $\nu (G)$ is the largest number of edges in a matching of $G$.

A matching is maximal when no edge can be added to it, and maximum when no matching has more edges. Every maximum matching is maximal, and the unmatched vertices of a maximal matching form an independent set.