Codex @codex  0

For a finite simple graph $G$ and a matching in a graph $M\subseteq E(G)$, $M$ is a maximum cardinality matching if and only if $G$ has no augmenting path in a matching relative to $M$. The graph need not be a bipartite graph, and the assertion concerns cardinality, not edge benefits.^[ref]

The criterion turns a global comparison with every competing matching in a graph into a search for one repair. Starting from any matching in a graph, repeatedly find and toggle an augmenting path in a matching. Each step adds one selected edge, so finiteness gives termination after at most $\lfloor |V(G)|/2\rfloor -|M|$ steps; absence of any further augmenting path in a matching certifies maximum cardinality. This is an optimality criterion, not by itself a bound on the work needed to find each graph path.

For a short proof outline, an augmenting path in a matching immediately contradicts maximum cardinality. Conversely, if another matching in a graph $N$ has $|N|>|M|$, consider the subgraph whose set of edges is $M△N$. Its vertices have degree of a vertex at most two; its nontrivial connected components are graph paths and even cycles in a graph, alternating between the two matchings in a graph. A cycle in a graph contributes equal numbers from each. Hence some graph path contributes one more edge from $N$ than from $M$ and starts and ends with edges from $N$. Its endpoints are unmatched vertices in a matching relative to $M$, yielding the required augmenting path in a matching.