[proofplan] We describe Edmonds' search as an alternating-forest algorithm with one extra operation: when the search finds an odd alternating cycle, it contracts that cycle to a single pseudovertex and continues in the contracted graph. The key point is the blossom [lifting lemma](/theorems/2437): contracting such a blossom preserves the existence of augmenting paths, and any augmenting path found after contraction can be lifted back to the original graph. If the exhausted search finds neither an augmenting path nor a blossom, the alternating-forest invariant rules out every possible first edge by which an augmenting path could leave the searched region. Finally, repeated augmentation terminates because each augmentation increases the cardinality of the matching by one, and the absence of augmenting paths characterizes maximum matchings. [/proofplan] [step:Define the alternating search and its invariant] Let $G=(V,E)$ be a finite loopless undirected graph and let $M \subset E$ be a [matching](/page/Matching). A vertex $v \in V$ is called $M$-exposed if no edge of $M$ is incident with $v$. An $M$-alternating path is a simple path whose consecutive edges alternate between $E \setminus M$ and $M$. An $M$-augmenting path is an $M$-alternating path whose endpoints are distinct $M$-exposed vertices and whose first and last edges lie in $E \setminus M$. The search maintains a rooted forest $F$: each component is rooted at an $M$-exposed vertex, and parent-child relations are those of these rooted trees. Thus the lowest common ancestor of two vertices in the same component means their deepest common vertex on the two root-to-vertex paths. Each vertex in $F$ is labelled even or odd according to its distance from its root in $F$. The maintained invariant is: Every even vertex $x$ in $F$ is joined to its root $r$ by an even-length $M$-alternating path $P_{r x}$ whose first edge, if present, lies in $E \setminus M$ and whose last edge, if present, lies in $M$. Every odd vertex $y$ in $F$ is joined to its root $r$ by an odd-length $M$-alternating path $P_{r y}$ whose first and last edges lie in $E \setminus M$. Initially $F$ consists of all $M$-exposed vertices as isolated even roots, so the invariant holds with paths of length $0$. The same initialization is used whenever the search is restarted in a contracted graph: every vertex exposed for the current matching, including a pseudovertex if it is exposed, is present as an even root. The search discipline is the following finite deterministic procedure. Maintain a set $S$ of processed edge objects, initially empty. While there is an edge $xy \in E \setminus S$ with $x$ labelled even, choose one such ordered incidence, insert the edge object $xy$ into $S$, and process it by the four cases below. When a new even vertex is added to the forest, its incident edges not already in $S$ become eligible for later processing. If a blossom is contracted, the algorithm restarts this same finite search in the contracted graph with the contracted matching, the newly initialized forest of all exposed roots, and an empty processed-edge set. Loops discarded by the contraction are removed from consideration, and parallel edge objects remain distinct. When the algorithm processes an edge $xy \in E$ with $x$ even, there are four cases. If $y$ is unlabelled, then $xy \notin M$, since an even non-root vertex is incident with its unique matched forest edge to its odd parent, while an even root is exposed. Add $y$ as an odd child of $x$. Since every exposed vertex in the current graph was initialized as an even root, the unlabelled vertex $y$ is not exposed. Let $yz \in M$ be the unique matching edge incident with $y$, and add $z$ as an even child of $y$. The invariant is preserved by appending the unmatched edge $xy$ and then the matched edge $yz$. If $y$ is even and lies in a different tree from $x$, then $xy \notin M$ by the same matching-edge uniqueness argument. Let $r_x$ and $r_y$ be the roots of the two trees. The path obtained by following $P_{r_x x}$, then the edge $xy$, and then the reverse of $P_{r_y y}$ is an $M$-augmenting path, because $r_x$ and $r_y$ are exposed and the parity of the two root paths makes the edge sequence alternate. If $y$ is even and lies in the same tree as $x$, let $b$ be the lowest common ancestor of $x$ and $y$ in $F$. The two tree paths from $b$ to $x$ and from $b$ to $y$, together with $xy$, form an odd cycle $B$. Along this cycle the edges alternate between $M$ and $E \setminus M$ except that the two cycle edges incident with $b$ both lie in $E \setminus M$. Such a cycle is called a blossom, and $b$ is called its base. If $y$ is odd, the edge gives no extension of the alternating forest. The search records that $xy$ has been processed and continues. [/step] [step:Contract a blossom without changing the augmenting-path question] Suppose $B \subset V$ is a blossom with base $b$. Write its vertices cyclically as \begin{align*} b=v_0, v_1, \dots, v_{2q}, v_0 \end{align*} for some integer $q \geq 1$, so that the two edges incident with $b$ on the cycle are not in $M$, and the remaining cycle edges alternate between $M$ and $E \setminus M$. Define the contracted graph $G/B=(V_B,E_B)$ as a finite loopless multigraph: replace all vertices of $B$ by a single pseudovertex $\beta$, retain each edge with both endpoints outside $B$ as the same edge object, and replace each edge from a vertex of $B$ to a vertex of $V \setminus B$ by a distinct edge object from $\beta$ to that outside vertex. Loops created by edges internal to $B$ are discarded. Parallel edges are retained distinctly, so matching membership is still a property of edge objects. Define the contracted matching $M_B \subset E_B$ by deleting the matching edges contained in the blossom and replacing any matching edge from $b$ to a vertex outside $B$ by the corresponding edge from $\beta$ to that outside vertex. [claim:Blossom contraction preserves augmenting paths] The graph $G$ has an $M$-augmenting path if and only if $G/B$ has an $M_B$-augmenting path. Moreover, every $M_B$-augmenting path in $G/B$ can be lifted effectively to an $M$-augmenting path in $G$. [/claim] [proof] First let $P$ be an $M$-augmenting path in $G$. Among all $M$-augmenting paths in $G$, choose $P$ so that the number of edges of $P$ with exactly one endpoint in $B$ is minimal, and subject to that choice so that the number of edges of $P$ is minimal. Contracting $B$ sends $P$ to a walk $W$ in $G/B$: every edge outside $B$ keeps its matching status, every edge from $B$ to $V \setminus B$ becomes the corresponding edge incident with $\beta$, and internal blossom edges disappear. We prove that $W$ is alternating at every occurrence of $\beta$ after deleting any consecutive repetitions of $\beta$ created by an internal subpath of $P$ lying entirely in $B$. Away from $\beta$, edge statuses still alternate because the corresponding edge sequence is unchanged from $P$. Consider an occurrence of $\beta$ with two adjacent surviving boundary edges. These two boundary edges cannot both be matched: every vertex of $B \setminus \{b\}$ is matched by an internal blossom edge, so no such vertex is incident with an external matching edge, and the matching property allows at most one external matching edge incident with the base $b$. It remains to exclude the case in which the two adjacent surviving boundary edges are both unmatched. Let those original boundary edges meet $B$ at vertices $u,w \in B$, possibly with $u=w$, and let $R$ be the subpath of $P$ between these two boundary vertices whose internal vertices lie in $B$. Because the two boundary edges are unmatched and $P$ alternates, the first and last edges of $R$, when present, are matched. Thus $R$ is an alternating path in the blossom whose endpoint incidences require matched blossom edges at both $u$ and $w$. We record the exact parity fact used here. Delete from the blossom cycle the vertex $b$ and the two unmatched cycle edges incident with $b$. The remaining edges form an alternating path \begin{align*} v_1, v_2, \dots, v_{2q} \end{align*} with matching edges precisely $v_1v_2, v_3v_4, \dots, v_{2q-1}v_{2q}$. Hence every vertex of $B \setminus \{b\}$ is incident with exactly one matched blossom edge, and the base $b$ is incident with no matched blossom edge on the cycle. Therefore a blossom-internal alternating path whose first and last incidences are matched can join two boundary vertices $u,w$ only when neither endpoint is $b$ and the unique matched blossom edge at $u$ and the unique matched blossom edge at $w$ both lie on the same simple $u$-to-$w$ arc of the cycle. In that case the complementary simple arc from $u$ to $w$ has first and last edges unmatched. Replacing $R$ by this complementary arc, together with the same two unmatched boundary edges, gives a simple $M$-alternating path with the same exposed endpoints and with no internal vertex outside $B$ changed. The replacement is simple because $P$ is simple, $R$ met the rest of $P$ only at $u$ and $w$, and the complementary blossom arc is contained in the cycle vertices of $B$ not used internally by $R$. This new augmenting path has the same boundary crossings with $B$ and is strictly shorter whenever $R$ was not already the complementary arc. If $R$ were already the complementary arc, then its first and last incidences would be unmatched, contradicting that the boundary edges on both sides are unmatched and $P$ alternates. Thus the replacement contradicts the choice of $P$ after refining the choice as follows: among all $M$-augmenting paths, choose one with the fewest boundary crossings with $B$, and subject to that, with the fewest edges. Hence adjacent surviving boundary edges at $\beta$ always have opposite matching status. Therefore the contracted walk $W$ is an $M_B$-alternating walk. Its endpoints are $M_B$-exposed: an exposed endpoint outside $B$ remains exposed after contraction, while if an exposed endpoint of $P$ lies in $B$, it must be the base $b$ because every vertex of $B \setminus \{b\}$ is matched by an internal blossom edge, and then the contracted endpoint is the exposed pseudovertex $\beta$. The first and last surviving edges are unmatched, so $W$ has exposed endpoints and first and last edges in $E_B \setminus M_B$. We now pass from the alternating walk $W$ to an alternating path. Let \begin{align*} W=(w_0,e_1,w_1,\dots,e_m,w_m) \end{align*} with $w_0$ and $w_m$ $M_B$-exposed and $e_1,e_m \in E_B \setminus M_B$. Among all $M_B$-alternating walks with these endpoint properties that are obtainable from $W$ by deleting closed subwalks, choose one, denoted $W_0$, with the fewest edges. Suppose $W_0$ repeats a vertex $z$, and choose two occurrences $w_i=w_j=z$ with $0\leq i<j\leq m$ and with $j-i$ minimal among repeated occurrences in $W_0$. If $j-i$ is even, delete the closed subwalk from $w_i$ to $w_j$. The edge before the deleted portion, when present, has the opposite matching status from the edge after the deleted portion, when present, because the deleted portion has even length and the original walk alternates. This produces a shorter alternating walk with the same exposed endpoints and the same unmatched first and last edges, contradicting minimality. It remains to rule out $j-i$ odd. Then the closed subwalk from $z$ back to $z$ has odd length and alternates. Its first and last edges have the same matching status. If that common status were matched, then the matching $M_B$ would contain two distinct edges incident with $z$, impossible. Hence the common status is unmatched. The two outside edges adjacent to the closed subwalk, when they exist, are matched by alternation. Since $M_B$ is a matching, there can be at most one matched edge incident with $z$; therefore, if both outside edges exist, they are the same edge object. Removing the closed subwalk together with one occurrence of this repeated matched edge gives a shorter alternating walk with the same exposed endpoints and unmatched end edges. If one outside edge is absent, then $z$ is an exposed endpoint of the walk, but the adjacent outside edge would be matched, contradicting that the first or last edge of an augmenting alternating walk is unmatched. Thus the odd case is impossible in a minimal walk. Therefore $W_0$ has no repeated vertex, and so $W_0$ is an $M_B$-augmenting path in $G/B$. Conversely, let $Q$ be an $M_B$-augmenting path in $G/B$. If $Q$ avoids $\beta$, then $Q$ is already an $M$-augmenting path in $G$. Suppose $Q$ contains $\beta$. Since $Q$ is simple, it uses either one edge incident with $\beta$, if $\beta$ is an endpoint, or two edges incident with $\beta$, if $Q$ passes through $\beta$. Choose, for each edge of $Q$ incident with $\beta$, the corresponding original edge in $G$ from an outside vertex to a vertex of $B$. We use the following parity property of the blossom cycle. For every vertex $u\in B\setminus\{b\}$ and for each prescribed status $\sigma\in\{M,E\setminus M\}$, exactly one of the two simple directed cycle arcs from $b$ to $u$ has all consecutive edges alternating and has terminal edge of status $\sigma$. Indeed, write $u=v_i$ with $1\leq i\leq 2q$. The forward arc $v_0,v_1,\dots,v_i$ and the backward arc $v_0,v_{2q},v_{2q-1},\dots,v_i$ both begin with an unmatched edge at $b$. Along each arc, after this first edge, the edge statuses alternate. Since the two arc lengths $i$ and $2q+1-i$ have opposite parity, their terminal edge statuses at $u$ are opposite. Thus exactly one arc has terminal status opposite to any prescribed outside edge status at $u$. If $Q$ has $\beta$ as an endpoint, then $\beta$ is $M_B$-exposed, so $b$ is $M$-exposed. Let $u \in B$ be the blossom vertex corresponding to the unique edge of $Q$ incident with $\beta$. If $u=b$, replace the endpoint $\beta$ by the vertex $b$ and add no internal blossom edge. If $u\neq b$, replace the endpoint $\beta$ by the unique base-to-$u$ blossom arc whose terminal edge status alternates with that outside edge. This produces an alternating path in $G$ whose new endpoint $b$ is exposed. If $Q$ passes through $\beta$, then exactly one of the two incident edges of $Q$ is matched and the other is unmatched. The matched incident edge must be the contracted image of the unique possible external matching edge at the base $b$; hence its original boundary vertex is $b$. Let $u \in B$ be the boundary vertex corresponding to the other, unmatched, incident edge. Replace the passage through $\beta$ by the unique base-to-$u$ blossom arc whose terminal edge status alternates with that unmatched outside edge. The edge at the base side is compatible because it is the external matched edge incident with $b$, while both cycle edges incident with $b$ are unmatched. Thus the resulting edge sequence alternates with respect to $M$. The replacement uses a simple arc inside the blossom and meets the rest of $Q$ only at its boundary vertices, because $Q$ is simple outside $\beta$. Therefore the lifted object is a simple $M$-alternating path with exposed endpoints. Thus it is an $M$-augmenting path in $G$. [guided] We prove that shrinking the blossom loses no information about augmenting paths. The blossom is an odd cycle \begin{align*} b=v_0, v_1, \dots, v_{2q}, v_0 \end{align*} whose base is $b$, whose two cycle edges incident with $b$ are unmatched, and whose remaining cycle edges alternate between matched and unmatched. The matching $M_B$ in the contracted graph is defined by removing the matching edges internal to the blossom and keeping the possible external matched edge incident with the base as an edge incident with the pseudovertex $\beta$. First suppose $P$ is an $M$-augmenting path in $G$. Contraction may turn a simple path into a walk, because $P$ can meet the blossom more than once. We therefore do two operations, and both must be justified. First collapse every visit of $P$ inside $B$ to the pseudovertex $\beta$. Matching status is preserved on every external edge. What needs checking is local alternation at $\beta$, since internal blossom edges have been deleted. The subtle point is that the collapsed sequence is not automatically alternating. Consider one occurrence of $\beta$ with two adjacent surviving boundary edges. These two edges cannot both be matched: every vertex of $B \setminus \{b\}$ is already matched by an internal blossom edge, and the matching property allows at most one external matched edge incident with the base $b$. If one boundary edge is matched and the other is unmatched, then the local alternation condition at $\beta$ is valid. What if the two adjacent surviving boundary edges are both unmatched? This is exactly the situation that must not be handled by a local exposure assertion: whether $\beta$ is exposed is a global fact about $M_B$, not a fact determined by the two adjacent edges of this occurrence. Instead, choose the original augmenting path $P$ with the fewest boundary crossings with $B$, and among those with the fewest edges. Assume two adjacent surviving boundary edges at $\beta$ were both unmatched. Let their original endpoints in $B$ be $u$ and $w$, and let $R$ be the part of $P$ from $u$ to $w$ whose internal vertices lie in $B$. Since the outside edges on both sides are unmatched and $P$ alternates, the first and last edges of $R$, when they exist, must be matched. Now inspect the blossom cycle directly. Removing the base $b$ and the two unmatched cycle edges incident with $b$ leaves the alternating path $v_1,v_2,\dots,v_{2q}$, whose matched edges are exactly $v_1v_2, v_3v_4, \dots, v_{2q-1}v_{2q}$. Thus each vertex of $B\setminus\{b\}$ has a unique matched blossom edge, while $b$ has none. An internal path whose endpoint incidences must both be matched is therefore forced to use the unique matched blossom edge at $u$ and the unique matched blossom edge at $w$; these two forced incidences lie on one of the two simple cycle arcs from $u$ to $w$. The other simple arc has unmatched first and last edges. Replace $R$ by that other arc. The two outside boundary edges are still present, and now each is followed or preceded by a blossom edge of the opposite matching status, so alternation is preserved. The exposed endpoints of the whole path do not change. The replacement is simple because the old path $P$ was simple, $R$ met the rest of $P$ only at $u$ and $w$, and the complementary cycle arc uses exactly the blossom vertices not used internally by $R$. It also keeps the same number of boundary crossings with $B$ and strictly reduces the number of edges; if it did not, then $R$ would already be the complementary arc, whose endpoint incidences are unmatched, contradicting the matched-incidence requirement forced by the two outside unmatched edges. This contradicts the refined minimal choice of $P$. Thus the contracted walk has no same-status adjacent boundary pair at $\beta$ and is an $M_B$-alternating walk with exposed endpoints and unmatched first and last edges. Second, we extract a simple path from this alternating walk. Among all alternating walks with exposed endpoints and unmatched first and last edges obtainable from $W$ by deleting closed subwalks, choose one $W_0$ with the fewest edges. If a repeated vertex occurs with an even number of intervening edges, deleting that closed even subwalk preserves alternation at the join, because the edge before the deletion and the edge after the deletion have opposite matching status. If a repeated vertex occurs with an odd number of intervening edges, the closed odd subwalk has first and last edges of the same status. They cannot both be matched, because $M_B$ is a matching. If they are both unmatched, then the outside adjacent edges, when present, are matched; the matching property forces the two outside matched edges at the repeated vertex to be the same edge object, so deleting the closed odd subwalk together with one copy of that matched edge again gives a shorter alternating walk with the same exposed endpoints and unmatched end edges. If one outside adjacent edge is absent, the repeated vertex is an exposed endpoint but the adjacent edge would be matched, contradicting the endpoint condition. Thus no repeated vertex can occur in $W_0$, and $W_0$ is an $M_B$-augmenting path. Now suppose $Q$ is an $M_B$-augmenting path in $G/B$. If $Q$ avoids $\beta$, there is nothing to lift. Assume $Q$ contains $\beta$. Because $Q$ is simple, it either has $\beta$ as an endpoint and uses one incident edge there, or passes through $\beta$ and uses two incident edges there. The internal replacement is always routed through the base $b$; this is the point that prevents an unsupported arbitrary $u$-to-$w$ assertion. Fix a boundary vertex $u\in B\setminus\{b\}$, and write $u=v_i$ with $1\leq i\leq 2q$. There are two simple directed cycle arcs from $b$ to $u$: the forward arc $v_0,v_1,\dots,v_i$ and the backward arc $v_0,v_{2q},v_{2q-1},\dots,v_i$. Each begins with an unmatched edge at $b$, and each alternates after that first edge because the blossom cycle alternates away from the base. The two arc lengths are $i$ and $2q+1-i$, which have opposite parity. Therefore the terminal edge statuses at $u$ are opposite. Given the outside edge at $u$, exactly one of these two arcs has terminal edge status opposite to that outside edge, and that is the compatible arc used in the lift. If the boundary vertex is $u=b$, the compatible replacement is the zero-edge path consisting only of the base $b$. If $\beta$ is an endpoint of $Q$, then $\beta$ is exposed for $M_B$, so $b$ is exposed for $M$. Let $u \in B$ be the blossom vertex corresponding to the unique outside edge of $Q$ incident with $\beta$. Replace $\beta$ by the compatible base-to-$u$ arc, interpreted as the zero-edge path when $u=b$. The new endpoint is $b$, which is exposed, and when $u\neq b$ the terminal edge of the chosen arc alternates with the outside edge at $u$. If $Q$ enters and leaves $\beta$, then one incident edge is matched and the other is unmatched, because $Q$ is alternating. The matched incident edge must be the contracted image of the unique possible external matched edge at the base $b$; therefore its original boundary vertex is $b$. Let $u \in B$ be the boundary vertex corresponding to the other incident edge, which is unmatched. Replace the segment through $\beta$ by the compatible base-to-$u$ arc. At the base side, the outside edge is matched and the first blossom edge is unmatched. At the $u$ side, the chosen terminal edge has the opposite status from the unmatched outside edge. Thus every consecutive pair of edges after the substitution alternates between $M$ and $E \setminus M$. The substituted arc is simple and lies inside $B$, while the rest of $Q$ is simple outside $\beta$. Therefore the lift is a simple $M$-alternating path with exposed endpoints. This proves both directions of the blossom [contraction lemma](/theorems/1981). [/guided] [/proof] [/step] [step:Iterate contractions until the search either finds a path or exhausts the graph] The algorithm applies the forest search described above. Whenever it finds a blossom, it contracts that blossom and restarts the search in the contracted graph with the contracted matching, the forest consisting of all currently exposed vertices as isolated even roots, and the processed-edge set empty. This restart preserves the alternating-forest invariant because each root is exposed and the required root-to-root path has length $0$. Since every contraction strictly decreases the number of vertices, only finitely many consecutive contractions can occur. Between two contractions, each search operation processes one previously unprocessed edge object incident with an even vertex in the current finite graph. Hence the search either finds an augmenting path or reaches a state in which every edge incident with every even vertex has been processed. If an augmenting path is found in a contracted graph, repeatedly apply the lifting procedure from the blossom contraction claim in reverse order of contraction. This produces an augmenting path in the original graph. It remains to justify the certificate produced by an exhausted search. Work in the final contracted graph, meaning the graph obtained after performing every blossom contraction encountered by the search and then processing every edge incident with every even vertex without finding either an augmenting path or another uncontracted same-tree even-even blossom. Suppose that an augmenting path \begin{align*} P=(p_0,e_1,p_1,\dots,e_m,p_m) \end{align*} existed, where $p_0$ and $p_m$ are exposed and $e_1,e_m\in E\setminus M$. Since all exposed vertices are roots of the alternating forest, $p_0$ is an even root. Let $j\geq 0$ be maximal such that the initial segment from $p_0$ to $p_j$ agrees with the unique forest path from the root $p_0$ to $p_j$. The index $j$ is well-defined because $j=0$ is admissible. It cannot be $m$, since then $p_m$ would be a distinct exposed root lying inside the same forest tree, impossible. Thus $j<m$. The parity of the forest path to $p_j$ agrees with the parity of the alternating path, so $p_j$ is even exactly when $j$ is even and odd exactly when $j$ is odd. Because $P$ starts with an unmatched edge, every edge $e_{j+1}$ with $j$ even is unmatched and every edge $e_{j+1}$ with $j$ odd is matched. If $j$ were odd, then $p_j$ is an odd forest vertex. By the forest invariant, its unique matched edge is the tree edge from $p_j$ to its even child. The path edge $e_{j+1}$ is matched, so matching uniqueness forces $e_{j+1}$ to be exactly that tree edge, and the initial segment would continue one step farther in the forest, contradicting the maximality of $j$. Therefore $j$ is even. Set $x=p_j$, $y=p_{j+1}$, and $xy=e_{j+1}$. The search is exhausted, so this edge incident with the even vertex $x$ has been processed. If $y$ was unlabelled when $xy$ was processed, then $xy\notin M$ and the algorithm added $y$ as an odd child of $x$ and then added the matched partner of $y$ as an even child. If $y$ is not the terminal exposed vertex, the next edge of $P$ is matched, so matching uniqueness forces that next edge to be the same matched forest edge; the forest agreement extends past $j$, a contradiction. If $y$ is terminal, then $xy$ itself gives an augmenting path from the root to the exposed vertex $y$, so the search would have returned it rather than exhausting. If $y$ was even in a different tree, processing $xy$ would have returned an augmenting path. If $y$ was even in the same tree, processing $xy$ would have contracted the resulting blossom; this cannot occur in the final exhausted graph by the preceding definition of that final state. If $y$ was odd, then the path reaches an already-labelled odd vertex through the unmatched edge $xy$. The next edge of $P$, unless $y$ is terminal, must be matched; by matching uniqueness it is the odd vertex's matched forest edge to its even child, so the forest agreement again extends past $j$. If $y$ is terminal, then $y$ is exposed and cannot be odd, since every odd forest vertex is incident with its matched forest edge. All cases contradict maximality of $j$ or exhaustion. Therefore the exhausted contracted graph contains no augmenting path. By the blossom contraction claim, reversing the contractions transfers nonexistence of augmenting paths back to the original graph. [/step] [step:Augmenting along a returned path increases the matching size by one] Let $P$ be an $M$-augmenting path. Define \begin{align*} M' := M \triangle E(P), \end{align*} where $E(P)$ denotes the set of edges of $P$ and $\triangle$ denotes [symmetric difference](/page/Symmetric%20Difference). Because $P$ alternates and starts and ends with unmatched edges, the path $P$ contains one more edge from $E \setminus M$ than from $M$. Replacing on $P$ the matched edges by the unmatched edges therefore increases the cardinality by one: \begin{align*} |M'| = |M| + 1. \end{align*} No vertex is incident with two edges of $M'$. Vertices outside $P$ keep their old matching status, internal vertices of $P$ exchange one incident matched edge for the adjacent incident unmatched edge, and the two exposed endpoints each gain exactly one incident matched edge. Hence $M'$ is a matching. [/step] [step:Use the absence of augmenting paths to certify maximality] We prove the standard augmenting-path criterion directly. Let $M$ be a matching with no $M$-augmenting path, and let $N$ be any other matching. Consider the spanning subgraph $H=(V,M \triangle N)$. Since each vertex is incident with at most one edge of $M$ and at most one edge of $N$, every vertex has degree at most $2$ in $H$. Therefore every connected component of $H$ is either an even cycle alternating between $M$ and $N$, an alternating path, or an isolated vertex. On an alternating cycle, the numbers of $M$-edges and $N$-edges are equal. On an alternating path, the number of $N$-edges can exceed the number of $M$-edges only if the path begins and ends with edges of $N \setminus M$. In that case its endpoints are not incident with any edge of $M$, because the endpoint edges belong to the matching $N$ and no adjacent edge of $M$ appears at the endpoint. Thus such a component would be an $M$-augmenting path. By hypothesis no such component exists. Therefore every component of $H$ contains at most as many $N$-edges as $M$-edges. Summing over all components of $H$, and noting that edges common to $M$ and $N$ contribute equally to both matchings outside $M \triangle N$, gives \begin{align*} |N| \leq |M|. \end{align*} Since $N$ was arbitrary, $M$ is a maximum matching. [/step] [step:Terminate the repeated algorithm with a maximum matching] Start with any matching $M_0$, for example $M_0=\varnothing$. At stage $k$, run the blossom search on $(G,M_k)$. If it returns an $M_k$-augmenting path $P_k$, define \begin{align*} M_{k+1} := M_k \triangle E(P_k). \end{align*} By the augmentation step, $M_{k+1}$ is a matching and $|M_{k+1}|=|M_k|+1$. Since $G$ is finite, every matching has cardinality at most \begin{align*} \frac{|V|}{2}. \end{align*} Hence this process can perform only finitely many augmentations. When it stops, the search has certified that the current matching has no augmenting path. By the augmenting-path criterion proved above, that matching is maximum. This proves both the correctness of the single search procedure and the correctness of the repeated Edmonds blossom algorithm. [/step]