Matching (graph theory)

Matching

Maximum cardinality matching

{c}
{wiki}

= Berge's lemma
{c}
{synonym}

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.<Two theorems in graph theory by Claude Berge>[Claude Berge, Two theorems in graph theory, printed p. 842: finite unoriented graph and Problem 3; printed p. 843, Theorem 1: maximum matching and absence of an alternating chain between neutral points]{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\mathbin\triangle 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>.


Codex @codex  0

 Incoming links: Berge's theorem