Correctness of Blossom Augmentation

Why Contraction Must Preserve Augmentation

Blossom contraction lets a search for an augmenting path work with a smaller graph. But a path found in that contracted graph is useful only if it can be expanded into a genuine augmenting path in the original graph. The key is to enter and leave each blossom along the correct arm: the arm from the base to an attachment vertex with even length. Once lifted, the path alternates between unmatched and matched edges, and flipping its edges increases the matching by exactly one.

All original graphs in this tutorial are finite and simple. A matching \(M\) is a set of edges no two of which share an endpoint. A vertex is exposed if it is incident with no edge of \(M\). An augmenting path for \(M\) is a path whose endpoints are exposed and whose edges alternate between edges outside \(M\) and edges in \(M\), starting and ending with edges outside \(M\). In particular, an augmenting path has odd length.

Write the cycle in order as \(b=v_0,v_1,\ldots,v_{2k},b\). Its two cycle edges at \(b\) are unmatched, and the edges along either direction alternate thereafter. For a vertex \(x\) on the cycle, there is one route from \(b\) to \(x\) of even length and one of odd length. The even route has length zero when \(x=b\); when \(x\ne b\), it starts with an unmatched edge and ends with a matched edge. Reversing that route gives a path from \(x\) to \(b\) that starts with a matched edge and ends with an unmatched edge. This last statement applies only when \(x\ne b\); for \(x=b\), the even route is the length-zero path from \(b\) to itself.

The Lifting and Flipping Results

Proof. First consider a path that passes through the contracted vertex. If the path arrives on an unmatched external edge, then it must leave on a matched edge. The matched external edge is incident with the base \(b\): every other blossom vertex is already matched on the cycle. Let \(x\) be the endpoint in the blossom of the arriving unmatched edge. Use the even route from \(x\) to \(b\). If \(x\ne b\), this reversed route starts with a matched edge and ends with an unmatched edge, so it fits between the arriving unmatched edge and the departing matched edge. If \(x=b\), the internal route has length zero, and the two external edges meet at \(b\) with the required unmatched-then-matched status.

In the other orientation, the path arrives on a matched external edge at \(b\) and leaves on an unmatched external edge whose endpoint in the blossom is \(x\). Use the even route from \(b\) to \(x\). If \(x\ne b\), that route starts unmatched and ends matched, fitting between the arriving matched edge and departing unmatched edge. If \(x=b\), again the internal route has length zero, and the two external edges have the required matched-then-unmatched status.

If the contracted vertex is an endpoint of the augmenting path, it is exposed in the contracted matching, so its base is exposed in the original matching. If the path reaches the blossom on an unmatched edge at \(x\), use the even route from \(x\) back to \(b\) and end there. The arriving edge is unmatched, and the route, if nonempty, starts matched and then alternates; its last edge is unmatched. Thus the lifted path ends at the exposed base. Reversing this reasoning handles a path that starts at the blossom. The routes used are simple arcs of the cycle, and the rest of the contracted path lies outside the blossom, so this replacement does not repeat a vertex. The same argument applies recursively when a route or path passes through a blossom contracted earlier: expand the innermost contracted blossoms first, preserving the status of each incident edge, and then apply the argument to the enclosing blossom. Hence the fully expanded path is a path in the original graph with the required alternation. \(\square\)

Proof. The lemma gives a path in the original graph that alternates, starts and ends with unmatched edges, and has exposed endpoints. Thus it is an augmenting path. Let it contain \(2r+1\) edges. In order along the path, the \(r+1\) edges in odd positions are outside \(M\), and the \(r\) edges in even positions are in \(M\). Define the flipped edge set by removing those \(r\) matched path edges and adding the \(r+1\) unmatched path edges.

At each internal path vertex, one incident path edge is added and the other is removed. Therefore exactly one of those two edges belongs to the new edge set at that vertex. At either endpoint, the sole path edge is added, and the endpoint was exposed before the flip. No edge outside the path changes, and no path vertex is incident with an unchanged matching edge, since the old path edges already alternated and the endpoints were exposed. Thus the new edge set is a matching. Its size is \(|M|-r+(r+1)=|M|+1\), as required. \(\square\)

Worked Lifts

Common Mistake: Choosing the Wrong Arm

Not every route around an odd cycle preserves the alternation needed for the lift. In the cycle \(b-a-c-d-e-b\) above, suppose an unmatched external edge arrives at \(a\). Taking the short route \(a-b\) is wrong: \(ab\) is unmatched, so the arriving edge and \(ab\) would be two consecutive unmatched edges. The correct route is the even route \(a-c-d-e-b\), whose first edge \(ac\) is matched and whose statuses then alternate. Its last edge \(eb\) is unmatched, as needed before the matched external edge at \(b\). The base case matters too: when the attachment vertex is \(b\) itself, the even route has length zero; it has no first or last edge to classify.

The lift and flip perform different jobs. Lifting proves that the contracted search has produced a valid augmenting path in the original graph. Flipping then uses alternation and exposed endpoints to prove that the matching condition is preserved and its size increases by one. A path that merely joins the contracted vertices, without these edge-status checks, is not enough.