[proofplan] First we verify that the cycle found by the alternating forest has exactly the blossom structure: the root-to-vertex paths have even length, share a common stem to the base, and then split into two alternating branches whose non-base vertices are matched internally. For the forward contraction direction, we orient an augmenting path so that its last exit from the blossom has unmatched phase, splice the forest stem and a correctly phased blossom route to the remaining suffix, and then contract the resulting alternating walk. Conversely, an augmenting path in $G/B$ is lifted by replacing the contracted vertex $\beta$ with the unique correctly phased arc inside the odd alternating cycle. [/proofplan] [step:Verify that the cycle formed by the two even vertices is an odd alternating blossom] Let $x,y\in V(F)$ be the two distinct even-level vertices joined by the non-tree edge in the theorem statement, and write $e:=\{x,y\}\in E(G)$. Let $M$ be viewed as a set of pairwise vertex-disjoint edges, as in the definition of a [matching](/page/Matching). An $M$-[alternating path](/page/Alternating%20Path) is a path whose consecutive edges alternate between membership in $M$ and non-membership in $M$, an $M$-[augmenting path](/page/Augmenting%20Path) is an $M$-alternating path whose two endpoints are exposed vertices, and an $M$-[alternating forest](/page/Alternating%20Forest) is a rooted forest whose roots are exposed and whose root-to-vertex paths are $M$-alternating. We use the additional alternating-forest convention stated in the theorem: every tree edge from an even-level vertex to an odd-level child lies outside $M$, and every tree edge from an odd-level vertex to an even-level child lies in $M$. Let $\ell:V(F)\to \mathbb{N}\cup\{0\}$ be the level function of the rooted forest $F$, so $\ell(v)$ is the number of edges in the unique path in $F$ from its root to $v$. Let $P_x$ and $P_y$ denote the unique root-to-$x$ and root-to-$y$ paths in $F$. Let $P_{x,b}$ denote the subpath of $P_x$ from $b$ to $x$, and let $P_{y,b}$ denote the subpath of $P_y$ from $b$ to $y$. We first prove that $b$ is even-level. If $b$ were odd-level, then in an alternating forest the unique matched edge incident with $b$ in the tree would be the edge from $b$ to its parent, and no child edge of $b$ could belong to a valid alternating branch: an edge from an odd-level vertex to an even-level child is in $M$, and a matching contains at most one edge incident with $b$. Since $P_x$ and $P_y$ split after their last common vertex $b$, the vertex $b$ must have two distinct child edges on the two branches unless one of $x,y$ equals $b$; if one of $x,y$ equals $b$, then $b$ is one of the even-level vertices by hypothesis. Hence $b$ is even-level in all cases. Since $x$ and $y$ are even-level vertices and $b$ is even-level, the lengths of $P_{x,b}$ and $P_{y,b}$ are even. The cycle \begin{align*} B = P_{x,b} \cup \{\{x,y\}\} \cup P_{y,b} \end{align*} has edge set size \begin{align*} |E(P_{x,b})| + 1 + |E(P_{y,b})|, \end{align*} which is odd. Because $F$ is an $M$-alternating forest rooted at exposed vertices, every tree edge from an even-level vertex to an odd-level child is outside $M$, and every tree edge from an odd-level vertex to an even-level child is in $M$. Thus each of the two branches from $b$ alternates in matching status and begins, when non-empty, with an edge outside $M$. We now verify that $e\notin M$. If $x$ is a non-root even-level vertex, then its tree edge to its odd-level parent belongs to $M$; if $x$ is a root, then $x$ is exposed and has no incident edge of $M$. The same statement holds for $y$. Thus, if $e$ belonged to $M$, then either a non-root endpoint would be incident with two distinct matching edges or a root endpoint would not be exposed. Both alternatives contradict the defining properties of a matching and of the rooted alternating forest. Hence $e\notin M$. Therefore the cycle alternates around $B$ except that the two cycle edges incident with $b$ are both outside $M$ when both branches are non-empty, and the same alternating pattern holds with the joining edge replacing the missing branch edge when one branch is empty. Each vertex of $B\setminus\{b\}$ has exactly one incident cycle edge in $M$, namely its parent edge if it is even-level and its child edge if it is odd-level. Hence every vertex of $B\setminus\{b\}$ is matched by $M$ to another vertex of $B$, so $B$ is an $M$-[blossom](/page/Blossom) with base $b$. [guided] Let us unpack why the parity and matching assertions follow from the search tree. Define the level function $\ell:V(F)\to \mathbb{N}\cup\{0\}$ by declaring $\ell(v)$ to be the number of edges in the unique path in $F$ from the root of the tree containing $v$ to $v$. In an alternating forest rooted at an exposed vertex, the root has level $0$, and along every root-to-vertex path the edge statuses alternate: the first edge is outside $M$, the second is in $M$, the third is outside $M$, and so on. Therefore vertices at even level are reached by paths of even length. The delicate point is the parity of the common vertex $b$. The vertices $x$ and $y$ are both even-level vertices in the same tree, and $b$ is the last common vertex of their root paths. If $b$ were odd-level, then the edge from the parent of $b$ to $b$ would already be the unique matching edge incident with $b$ in the forest. Any child edge from $b$ to an even-level child would also have to belong to $M$, contradicting that $M$ is a matching if there were a branch continuing below $b$. Since the two root paths split at $b$, this rules out an odd-level split. If one of $x,y$ equals $b$, then $b$ is even-level because $x$ and $y$ are even-level by hypothesis. Thus $b$ is even-level. Let $P_{x,b}$ be the subpath from $b$ to $x$, and let $P_{y,b}$ be the subpath from $b$ to $y$. Since $\ell(x)$, $\ell(y)$, and $\ell(b)$ are even, both branch lengths are even: \begin{align*} |E(P_{x,b})| \equiv \ell(x)-\ell(b) \equiv 0 \pmod 2. \end{align*} Likewise, \begin{align*} |E(P_{y,b})| \equiv \ell(y)-\ell(b) \equiv 0 \pmod 2. \end{align*} Adding the extra edge $\{x,y\}$ therefore makes the total cycle length odd: \begin{align*} |E(B)| = |E(P_{x,b})|+|E(P_{y,b})|+1. \end{align*} Now consider the matching pattern. On each non-empty branch starting at $b$, the first edge away from $b$ is outside $M$, because it goes from an even-level vertex to an odd-level child. The next edge is in $M$, and the pattern continues. Since $x$ and $y$ are even-level vertices, the last branch edges entering $x$ and $y$ are in $M$ unless the branch has length $0$. The joining edge $\{x,y\}$ is outside $M$, because both $x$ and $y$ are even-level vertices and their matching edges, if present in the tree, are the edges to their odd-level parents. Thus the cycle alternates except at the base $b$, where the two incident blossom edges in the non-degenerate split case are both outside $M$. Finally, every non-base vertex on either branch is paired by exactly one cycle edge belonging to $M$. Odd-level vertices are matched to their even-level children in the forest, and even-level non-base vertices are matched to their odd-level parents. Hence all vertices of $B\setminus\{b\}$ are matched inside $B$, which is precisely the [blossom](/page/Blossom) condition with base $b$. [/guided] [/step] [step:Record the internal routing property of an odd alternating blossom] [claim:Every blossom vertex has a correctly phased route from the base] Let $v\in V(B)$. If $v=b$, the empty route from $b$ to $b$ is allowed. If $v\neq b$, there is a unique simple route in $B$ from $b$ to $v$ whose first edge is outside $M$, whose consecutive edges alternate in membership in $M$, and whose last edge belongs to $M$. [/claim] [proof] If $v=b$, the assertion is the empty-route convention. Suppose $v\neq b$. By construction, the cycle $B$ is the union of the two tree branches $P_{x,b}$ and $P_{y,b}$ together with the unmatched joining edge $e=\{x,y\}$. The two tree branches from $b$ have even length, start with an edge outside $M$ when non-empty, and alternate in matching status. Hence, on each branch, the unique route from $b$ to a non-base vertex at even distance from $b$ ends with an edge in $M$, while the unique route from $b$ to a non-base vertex at odd distance from $b$ ends with an edge outside $M$. Let $v$ lie on one of the two branches. If the branch route from $b$ to $v$ ends with an edge in $M$, that route is the required route. If it ends with an edge outside $M$, take the other branch from $b$ to its endpoint, then traverse the joining edge $e$, and then traverse the original branch backwards from its endpoint to $v$. The other branch has even length and ends with an edge in $M$, the joining edge $e$ is outside $M$, and the reversed tail on the original branch continues the alternating pattern until it reaches $v$ through the unique cycle edge of $M$ incident with $v$. Thus this second route is alternating from $b$ to $v$, starts outside $M$, and ends in $M$. The two simple routes from $b$ to $v$ have opposite parity in the odd cycle $B$, and an alternating route starting outside $M$ ends in $M$ exactly when it has even positive length. Therefore exactly one of the two routes has the required final matched status. [/proof] [/step] [step:Define the contraction and the contracted matching] Let $\beta$ be a new vertex not in $V(G)$. Define the contracted graph $G/B$ as the graph with vertex set \begin{align*} V(G/B)=(V(G)\setminus V(B))\cup\{\beta\}. \end{align*} For every edge $\{u,w\}\in E(G)$ with $u,w\notin V(B)$, retain the edge $\{u,w\}$ in $G/B$. For every edge $\{u,w\}\in E(G)$ with $u\in V(B)$ and $w\notin V(B)$, retain the edge $\{\beta,w\}$ in $G/B$. Edges with both endpoints in $V(B)$ become loops at $\beta$ and are discarded, since loops cannot lie on an augmenting path. Parallel edges, if produced by the contraction, are allowed as distinct edges carrying their original matching status. Define the quotient map on vertices as the map $q:V(G)\to V(G/B)$ such that $q(z)=\beta$ for $z\in V(B)$ and $q(z)=z$ for $z\notin V(B)$. Define the quotient map on non-loop edges as the map $q_E$ whose domain is the set of edges of $G$ with not both endpoints in $V(B)$ and whose value on an edge $a=\{u,w\}$ is the edge of $G/B$ with endpoints $q(u)$ and $q(w)$ carrying the identity of the original edge $a$. The contracted matching $M/B$ is obtained from $M$ by deleting every matching edge with both endpoints in $V(B)$ and applying $q_E$ to every remaining matching edge. Parallel edges in $G/B$ are therefore distinguished by their original edge identities, and the matching status of such an edge means membership of its original edge in $M$. Since every vertex of $B\setminus\{b\}$ is matched by an edge of $M$ internal to $B$, the only possible matching edge of $M$ incident with $V(B)$ and not internal to $B$ is the edge incident with the base $b$; hence $M/B$ is again a matching in the [contraction](/page/Graph%20Contraction) $G/B$. [/step] [step:Contract an augmenting path by proving the required local normalization] Assume that $G$ has an $M$-augmenting path. Choose one and write it as \begin{align*} P=(v_0,e_1,v_1,\dots,e_k,v_k) \end{align*} with exposed endpoints $v_0$ and $v_k$. If $P$ avoids $V(B)$, then the same vertex and edge sequence is an $M/B$-augmenting path in $G/B$. Suppose that $P$ meets $V(B)$. Let $r$ be the exposed root of the tree of $F$ containing $B$, and let $H$ be the tree path in $F$ from $r$ to $b$. If $H$ is non-empty, it starts with an edge outside $M$ and ends with an edge in $M$, because $r$ and $b$ are even-level vertices. If $H$ is empty, then $r=b$ and the base is exposed. Choose an orientation of $P$ with the following property. Let $v_j$ be the last vertex of the oriented path that lies in $V(B)$. If $j<k$, then the exit edge $e_{j+1}$ is outside $M$. Such an orientation exists: every exterior edge incident with a non-base vertex of $B$ is outside $M$, because that non-base vertex is matched internally in the blossom. The only exterior edge incident with $B$ that can belong to $M$ is the possible exterior matching edge at the base $b$. Hence at most one of the two oriented last-exit edges, obtained from the two possible orientations of $P$, can be matched. If $P$ has an endpoint in $B$, that endpoint must be $b$, since all vertices of $B\setminus\{b\}$ are matched internally; then there is no exit edge to check. Reversing $P$ if necessary, assume this orientation has been chosen. Let $v_j$ be the last blossom vertex in this orientation, and let $T$ be the suffix \begin{align*} T=(v_j,e_{j+1},v_{j+1},\dots,e_k,v_k), \end{align*} where the suffix is just the vertex $v_j$ if $j=k$. By definition of $j$, no vertex after $v_j$ in $T$ lies in $V(B)$. If $v_j=b$, let $R$ be the empty route from $b$ to $v_j$. If $v_j\neq b$, let $R$ be the route from $b$ to $v_j$ given by the routing claim: it starts with an edge outside $M$, alternates inside the blossom, and ends with an edge in $M$. Concatenate the forest stem $H$, the route $R$, and the suffix $T$, identifying the common endpoints $b$ and $v_j$. This gives a finite $M$-alternating walk from the exposed vertex $r$ to the exposed vertex $v_k$. Indeed, the join between $H$ and $R$ is alternating because $H$, when non-empty, ends with an edge in $M$ and $R$, when non-empty, starts outside $M$. The join between $R$ and $T$ is alternating because either $j=k$, or the chosen orientation gives $e_{j+1}\notin M$ while $R$ ends in $M$ when $v_j\neq b$. If $v_j=b$, then either $H$ is empty and the first edge of $T$ is outside $M$, or $H$ ends in $M$ and the chosen orientation again gives $e_{j+1}\notin M$. Now contract this alternating walk. Internal edges of the blossom route $R$ become loops at $\beta$ and are discarded, while the stem $H$ and the suffix $T$ keep their matching statuses under $q_E$. Hence the contracted sequence is a finite $M/B$-alternating walk in $G/B$. Its endpoints are exposed with respect to $M/B$: the endpoint $v_k$ is exposed in $G$ and lies outside $B$ unless $j=k$, while the starting endpoint is $r$ if $r\notin B$ and is $\beta$ if $r=b$. In the latter case $b$ is exposed in $M$, so $\beta$ is exposed in $M/B$. [claim:An alternating walk with exposed endpoints contains an augmenting path] Let $W$ be a finite $N$-alternating walk in a graph, where $N$ is a matching, and suppose the first and last vertices of $W$ are exposed with respect to $N$. Then $W$ contains a simple $N$-augmenting path. [/claim] [proof] Write \begin{align*} W=(w_0,f_1,w_1,\dots,f_m,w_m), \end{align*} where $w_0$ and $w_m$ are exposed with respect to $N$, $f_t=\{w_{t-1},w_t\}$ for $1\leq t\leq m$, and the edge statuses of $f_1,\dots,f_m$ alternate. Since $w_0$ and $w_m$ are exposed, the first and last edges, when they exist, satisfy $f_1\notin N$ and $f_m\notin N$. Among all finite $N$-alternating walks \begin{align*} Z=(z_0,h_1,z_1,\dots,h_s,z_s) \end{align*} whose endpoints $z_0,z_s$ are exposed with respect to $N$ and whose first and last edges, when they exist, lie outside $N$, choose one with $s$ minimal. Such a walk exists because $W$ itself has these properties. We prove that $Z$ is simple. Suppose $z_a=z_c$ for some $0\leq a<c\leq s$, and choose such a pair with $c-a$ minimal. Delete the closed subwalk \begin{align*} (z_a,h_{a+1},z_{a+1},\dots,h_c,z_c) \end{align*} and concatenate the remaining prefix and suffix. The resulting finite walk is \begin{align*} Z'=(z_0,h_1,z_1,\dots,z_a,h_{c+1},z_{c+1},\dots,h_s,z_s), \end{align*} with the evident omissions when $a=0$ or $c=s$. If $a=0$, then $z_c=z_0$ is exposed. The edge $h_{c+1}$, when it exists, cannot belong to $N$, because no edge of $N$ is incident with the exposed vertex $z_0$. Hence $Z'$ still begins with an unmatched edge. If $c=s$, the same argument at the exposed vertex $z_s=z_a$ shows that $h_a$, when it exists, is outside $N$, so $Z'$ still ends with an unmatched edge. It remains to check alternation at the only possible new splice, which occurs when $a>0$ and $c<s$. The two spliced edges are $h_a$ and $h_{c+1}$, both incident with the same vertex $z_a=z_c$. If they both belonged to $N$, then the matching $N$ would contain two distinct edges incident with one vertex, impossible. If they both lay outside $N$, then the alternating sequence around the deleted closed subwalk forces the two edges of the deleted subwalk incident with $z_a=z_c$, namely $h_{a+1}$ and $h_c$, to belong to $N$. These are distinct matching edges incident with the same vertex, again impossible. Therefore $h_a$ and $h_{c+1}$ have opposite matching status, and the concatenated walk $Z'$ is still $N$-alternating. The endpoints of $Z'$ are the same exposed vertices as the endpoints of $Z$, and its first and last edges, when present, remain outside $N$ by the endpoint check above. Also $Z'$ has fewer edges than $Z$, contradicting the minimal choice of $Z$. Thus $Z$ has no repeated vertices. It is an $N$-alternating simple path whose endpoints are exposed with respect to $N$, so it is an $N$-augmenting path. [/proof] Applying the walk-extraction claim with $N=M/B$ gives a simple $M/B$-augmenting path in $G/B$. Therefore $G/B$ has an $M/B$-augmenting path. [/step] [step:Lift an augmenting path in the quotient through the blossom] Assume that $G/B$ has an $M/B$-augmenting path, denoted \begin{align*} P'=(u_0,g_1,u_1,\dots,g_r,u_r). \end{align*} If $P'$ avoids $\beta$, then the same vertex and edge sequence is an $M$-augmenting path in $G$, because every edge of $P'$ is an unchanged edge outside $B$ and its matching status is unchanged. Suppose that $P'$ contains $\beta$. Since $P'$ is simple, $\beta$ is either an endpoint or has exactly two incident path edges. Each path edge incident with $\beta$ is the quotient of an edge of $G$ joining a vertex outside $B$ to a vertex of $B$. If such an incident quotient edge belongs to $M/B$, then its lift is the unique matching edge of $M$ incident with the base $b$ outside $B$, because every vertex of $B\setminus\{b\}$ is matched by an edge of $M$ internal to $B$. Thus every matched exterior incidence at $\beta$ lifts at $b$. If $\beta$ is internal in $P'$, the two incident path edges have opposite matching status. Orient the local segment through $\beta$ so that the matched exterior edge is incident with $b$ and the unmatched exterior edge lifts to an edge incident with some vertex $v\in V(B)$. If $v=b$, replace $\beta$ by $b$. If $v\neq b$, insert the route from $b$ to $v$ given by the routing claim. That route starts outside $M$ and ends in $M$; therefore, when traversed from $b$ to $v$, it follows the matched exterior edge at $b$ with an unmatched edge and reaches the unmatched exterior edge at $v$ through a matched edge. If the quotient path is oriented in the opposite direction, use the same route in reverse. The reversed route starts with a matched edge at $v$ and ends with an unmatched edge at $b$, so the alternating pattern is again preserved at both joins. If $\beta$ is an endpoint of $P'$, then $\beta$ is exposed in $M/B$, so $b$ is exposed in $M$ by the definition of the contracted matching. Let the unique path edge adjacent to $\beta$ lift to an edge incident with $v\in V(B)$. If $v=b$, replace $\beta$ by $b$. If $v\neq b$, then the adjacent exterior edge is outside $M$, since $v$ is matched internally in $B$; insert the route from $b$ to $v$ whose last edge belongs to $M$. The lifted path starts at the exposed vertex $b$, follows an alternating route ending with a matched edge, and then exits along the adjacent unmatched exterior edge. In every case the replacement uses a simple route inside the cycle $B$, preserves the matching status alternation at each join, and leaves all vertices outside $B$ unchanged. Since $P'$ is simple, no outside vertex is repeated after the lift. The inserted route lies entirely in $B$, and $P'$ contains $\beta$ only once, so no blossom vertex used by the inserted route appears elsewhere in the lifted sequence. Hence the lifted sequence is a simple path. Endpoints outside $B$ remain exposed in $G$, and an endpoint $\beta$ lifts to the exposed base $b$. Therefore the lifted path is an $M$-augmenting path in $G$. [/step] [step:Conclude the equivalence] The first direction shows that every $M$-augmenting path in $G$ yields an $M/B$-augmenting path in the contracted graph $G/B$. The second direction shows that every $M/B$-augmenting path in $G/B$ lifts to an $M$-augmenting path in $G$. Hence $G$ has an $M$-augmenting path if and only if $G/B$ has an $M/B$-augmenting path. [/step]