Contracting and Expanding a Blossom

Why Contract an Odd Alternating Cycle?

In a general graph, an augmenting path may be difficult to find because alternating paths can encounter odd cycles. A blossom packages one particular kind of odd cycle: its edges alternate around the cycle except at the base, where two consecutive cycle edges are unmatched. Contracting the cycle turns it into one vertex. The contraction is useful only if it preserves the question that matters: whether the current matching can be augmented.

All graphs below are finite and simple. A matching $M$ is a set of pairwise vertex-disjoint edges. A vertex is exposed by $M$ if it is incident to no edge of $M$. An augmenting path for $M$ is a path whose edges alternate between edges outside $M$ and edges in $M$, beginning and ending with edges outside $M$, and whose endpoints are exposed by $M$. Such a path has one more edge outside $M$ than in $M$.

Definition: Let $M$ be a matching in $G$. A blossom $B$ for $M$ is an odd cycle with vertices $b,v_1,\ldots,v_{2k}$ in cyclic order, where $k\ge1$, such that $$ bv_1,\ v_2v_3,\ v_4v_5,\ldots,v_{2k-2}v_{2k-1} \notin M,\qquad v_1v_2,\ v_3v_4,\ldots,v_{2k-1}v_{2k}\in M, $$ and $bv_{2k}\notin M$. The vertex $b$ is the base. It may be exposed, or it may be matched by an edge from $b$ to a vertex outside $B$. No other vertex of the cycle is matched to a vertex outside $B$.

Thus the cycle has $2k+1$ edges and exactly $k$ of them belong to $M$. The two cycle edges incident with the base are both outside $M$. A chord or other edge of the graph between vertices of $B$ does not affect this definition; only the specified cycle edges and matching incidences matter.

Contracting the Blossom

Contract $B$ to one new vertex $\beta$: replace all vertices of $B$ by $\beta$, retain edges between vertices outside $B$, and turn every edge from $B$ to a vertex outside $B$ into an edge incident with $\beta$. Delete loops and identify parallel edges, so the resulting graph $H$ is simple. Define $M'$ by deleting the $k$ matching edges of the cycle from $M$, retaining all matching edges outside $B$, and replacing a matching edge from $b$ to the outside by its corresponding edge from $\beta$. The base condition ensures that no other matching edge crosses from $B$ to its exterior.

Theorem (Blossom Contraction Lemma): With $G,M,B,H,\beta,M'$ as above, $M$ has an augmenting path in $G$ if and only if $M'$ has an augmenting path in $H$. Moreover, every $M'$-augmenting path in $H$ can be expanded to an $M$-augmenting path in $G$.

We prove the equivalence by comparing maximum matching sizes, then give an explicit path-lifting construction. The comparison avoids a common trap: the direct image of an augmenting path under contraction need not itself alternate.

Lemma: The maximum matching sizes satisfy $\nu(G)=\nu(H)+k$.

Proof. First take any matching $N$ of $H$. If $N$ uses an edge $\beta x$, choose an original edge $wx$ that produced it, with $w\in B$. The cycle with $w$ deleted is a path on $2k$ vertices, so its consecutive edges give a matching of size $k$ covering every vertex of $B\setminus\{w\}$. Combine those $k$ edges with the original edge $wx$ and with the edges of $N$ outside $\beta$. They are pairwise disjoint, giving a matching of $G$ of size $|N|+k$. If $N$ does not use $\beta$, choose any $w\in B$, use the same size-$k$ matching of $B\setminus\{w\}$, and combine it with $N$. Thus $\nu(G)\ge\nu(H)+k$.

Conversely, let $L$ be any matching of $G$. Write $j$ for the number of its edges with both endpoints in $B$, $q$ for the number with exactly one endpoint in $B$, and $r$ for the number with both endpoints outside $B$. Since $L$ is a matching, $q$ is either $0$ or $1$, and $j\le k$, because $B$ has $2k+1$ vertices. Contract the one crossing edge if $q=1$, and keep the $r$ outside edges. These edges form a matching of $H$: if a crossing edge is present, no other edge of $L$ uses its outside endpoint. This matching has size $q+r=|L|-j\ge |L|-k$. Applying this to a maximum matching of $G$ gives $\nu(H)\ge\nu(G)-k$. Together the two inequalities yield $\nu(G)=\nu(H)+k$. $\square$

By definition of $M'$, its size is $|M'|=|M|-k$. Consequently, $$ \nu(G)-|M|=\nu(H)+k-|M|=\nu(H)-|M'|. $$ The standard Berge lemma, established in the earlier material on augmenting paths, says that a matching is not maximum if and only if it has an augmenting path. The displayed equality therefore proves the two-way existence claim. The remaining construction explains how to lift a particular contracted augmenting path.

How to Lift a Contracted Path

For every vertex $w$ of the blossom, there is an even-length cycle path from $b$ to $w$ that starts with an edge outside $M$ and ends with an edge in $M$. For $w=b$, this is the length-zero path. For $w\ne b$, the two cycle arcs from $b$ to $w$ have lengths of opposite parity, so exactly one has even length. The even arc has the stated edge pattern: starting from $b$, its first edge is unmatched; the cycle statuses alternate along the arc; and its last edge is matched. This follows directly from the specified alternating cycle edges. In particular, the claim concerns the even arc only; it does not assert that both arcs alternate.

Choose original representatives.
For each edge $\beta x$ of the contracted path, select an original edge $wx$ with $w\in B$ that produced it. If the edge is in $M'$, its original representative is the base edge $bx$.

Replace an exposed endpoint.
If $\beta$ is an endpoint of the augmenting path, it is exposed by $M'$, hence $b$ is exposed by $M$. Replace the final edge $x\beta$, represented by $xw$, with $xw$ followed by the even cycle path from $w$ back to $b$.

Replace an internal visit.
If $\beta$ is internal, the path uses one matched edge $\beta z$ and one unmatched edge $\beta x$. The matched edge is the base edge $bz$. Replace the passage $z,\beta,x$ by $z,b$, then the even cycle path from $b$ to the representative $w$ of $\beta x$, then $w,x$.

Proof of the lifting claim. A contracted augmenting path has no repeated vertices, so it visits $\beta$ at most once. If it visits $\beta$ internally, alternation forces one incident edge to be in $M'$ and the other outside $M'$. The matched edge is the base edge $bz$, and the other edge has a representative $wx\notin M$. In the replacement, $zb$ is matched; the even cycle path from $b$ to $w$ starts unmatched and ends matched; and $wx$ is unmatched. Thus the entire replacement alternates, with the same status at both joins as in the contracted path. If $\beta$ is an endpoint, it is exposed, so the edge leading to it is unmatched; the reverse of the even cycle path from $b$ to $w$ ends at $b$ with an unmatched edge, as required for an exposed endpoint. In both cases the replacement uses distinct cycle vertices and no outside vertex already occurs twice, because the contracted path is simple and $\beta$ occurs at most once. The result is a simple alternating path with the original exposed endpoints. It is therefore an $M$-augmenting path. $\square$

Worked Examples

Worked Example: The Direct Image Need Not Alternate

Let $G$ have vertex set $\{b,a,c,x,y\}$ and edge set $\{ba,ac,cb,xa,cy\}$. Take $M=\{ac\}$. The triangle $b,a,c,b$ is a blossom with base $b$, and $k=1$.

The path $x,a,c,y$ has edge statuses $N,M,N$, where $N$ means outside $M$ and $M$ means in $M$. Its endpoints $x,y$ are exposed, so it is an augmenting path. After contraction the graph $H$ has vertices $\{\beta,x,y\}$, edges $\{\beta x,\beta y\}$, and matching $M'=\varnothing$. The direct image $x,\beta,y$ has statuses $N,N$, so it is not alternating.

But $x,\beta$ is an augmenting path in $H$: both endpoints are exposed and its only edge is outside $M'$. It lifts using the original representative $xa$ and the even cycle path $a,c,b$. The lifted path is $x,a,c,b$, with statuses $N,M,N$; its endpoints $x,b$ are exposed.

Check: $H$ has maximum matching size $1$, since either edge can be chosen but both share $\beta$. The original graph has the matching $\{xa,cb\}$ of size $2$. The lemma gives $\nu(G)=\nu(H)+1=2$, consistent with this matching; the graph has five vertices, so no matching can have more than two edges.

Worked Example: Lifting Through a Matched Base

Let $G$ have vertex set $\{a,b,c,x,z,y\}$ and edge set $\{ab,ac,bc,bz,xa,zy\}$. Let $M=\{ac,bz\}$. The cycle $b,a,c,b$ is a blossom with base $b$, and $b$ is matched externally to $z$.

After contraction, $H$ has vertices $\{\beta,x,z,y\}$, edges $\{\beta x,\beta z,zy\}$, and matching $M'=\{\beta z\}$. The path $x,\beta,z,y$ has statuses $N,M,N$. Its endpoints $x,y$ are exposed, so it is an augmenting path for $M'$.

Use $xa$ as the representative of $\beta x$. The even cycle path from $b$ to $a$ is $b,c,a$, with statuses $N,M$. Replacing the passage through $\beta$ gives $x,a,c,b,z,y$. Its statuses are $N,M,N,M,N$, and its endpoints $x,y$ are exposed by $M$.

Check: The lifted path has five edges, of which the second and fourth are in $M$; hence it has three edges outside $M$ and two inside. Flipping those five edges increases the matching size by $3-2=1$, as an augmenting path must.

Worked Example: A Five-Cycle and the Matching-Size Offset

Let $G$ have vertex set $\{b,v_1,v_2,v_3,v_4,x,y\}$ and edge set $\{bv_1,v_1v_2,v_2v_3,v_3v_4,v_4b,xv_2,yv_3\}$. Take $M=\{v_1v_2,v_3v_4\}$. The five-cycle is a blossom with base $b$ and $k=2$.

Contracting it gives vertices $\{\beta,x,y\}$, edges $\{\beta x,\beta y\}$, and $M'=\varnothing$. The contracted graph has maximum matching size $1$, because its two edges meet at $\beta$. In $G$, the edges $\{bv_1,v_2x,v_3v_4\}$ form a matching of size $3$. Since $G$ has seven vertices, a matching has at most $\lfloor7/2\rfloor=3$ edges, so $\nu(G)=3$. Thus $\nu(G)=\nu(H)+k=1+2=3$.

The original matching $M$ has size $2$, while $M'$ has size $0$. The path $x,\beta$ augments $M'$; its lift is $x,v_2,v_1,b$, whose statuses are $N,M,N$. The endpoints $x,b$ are exposed by $M$, and flipping the path gives the size-$3$ matching displayed above.

Check: The cycle contributes exactly $k=2$ matching edges to $M$, and contraction removes those two edges. The maximum matching sizes differ by exactly $2$, as the lemma states.

Common Pitfall and Why the Construction Matters

Do not claim that contracting the part of an augmenting path inside a blossom automatically leaves an alternating path. In the first example, the original path has statuses $N,M,N$, but its direct image has statuses $N,N$. The correction is not to assume that the image alternates; instead, use the equivalence proof to establish existence and use the lifting construction for a contracted path. In that example, the contracted path $x,\beta$ works, even though the direct image of the original path does not.

It is also unsafe to reason that both cycle arcs from the base to a vertex alternate. The blossom definition guarantees the specified alternating pattern around the cycle, with two consecutive unmatched edges at the base. For a lift, choose the even-length arc: it starts unmatched at the base and ends matched at the chosen cycle vertex. That specific pattern is what makes the joins alternate in the construction.

Blossom contraction is therefore more than a change of notation. The size identity $\nu(G)=\nu(H)+k$ proves that the matching’s deficit from maximum is unchanged, while the even-arc construction shows concretely how a contracted augmenting path becomes one in the original graph.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

Why can an augmenting path in $G$ have a direct image under contraction that is not alternating?
Explain why $B-w$ has a matching of size $k$ for every vertex $w$ on a blossom cycle.
If $\beta$ is internal to an augmenting path in $H$, why must one incident path edge be matched and the other unmatched?
For the five-cycle example, write the edge statuses on the even cycle path from $b$ to $v_2$.
Which two facts establish the two directions of the blossom contraction lemma: the matching-size identity or the explicit lifting construction?