Why Search Needs Blossoms
For a bipartite graph, an alternating search can grow from an unmatched vertex by following edges outside the matching and then edges in the matching. In a general graph, an edge joining two even-level search vertices can create an odd cycle. This is a blossom. Treating that edge as an ordinary discovery can invalidate the alternating structure, so Edmonds’ search contracts the blossom and continues in a smaller graph.
Throughout, graphs are finite and simple, and \(M\) is a matching: a set of pairwise vertex-disjoint edges. An edge is unmatched if it is not in \(M\). An augmenting path for \(M\) is a path whose first and last vertices are unmatched by \(M\), and whose edges alternate between outside and inside \(M\), starting and ending with an edge outside \(M\). Replacing the matching edges of such a path by its other edges increases the matching size by one.
We describe a search from one unmatched root \(r\). Run it again from another unmatched vertex if needed. This is enough to find an augmenting path if one exists: an augmenting path begins at an unmatched vertex, and that vertex can be chosen as the root of its own search. A vertex can be labelled only once in a given search.
The Search Rules
Scan edges incident to \(S\)-vertices. Do not scan an edge in \(M\) from an \(S\)-vertex: except at the root, its matching edge is its parent edge to a \(T\)-vertex. For an edge \(uv\) with \(u\) labelled \(S\) and \(uv\notin M\), use these rules:
- If \(v\) is unmatched, the tree path from \(r\) to \(u\), followed by \(uv\), is an augmenting path. Stop.
- If \(v\) is matched and not yet labelled, label \(v\) as \(T\), then label its matched partner as \(S\) and add that matched edge to the tree.
- If \(v\) is already labelled \(S\), the edge joins two \(S\)-vertices. Find their lowest common ancestor in the rooted tree. The two tree paths from that ancestor to the endpoints, together with \(uv\), form a blossom. Contract it and continue the search in the contracted graph.
- If \(v\) is labelled \(T\), no new label is needed from this edge.
The base of a blossom is the common ancestor in rule 3. It is an \(S\)-vertex. The tree paths from the base to the two endpoints each have even length: they alternate from \(S\) to \(T\) to \(S\), and end at \(S\). Adding the edge between the endpoints gives an odd cycle. The blossom’s matching edges alternate with its unmatched edges except at the base, whose two cycle edges are unmatched.
For this single-root description the base may be the root, in which case the contracted supervertex is unmatched and becomes the new root. If the base is not the root, its matching edge to its parent \(T\)-vertex remains the matching edge incident with the supervertex. The contracted search uses the inherited matching, not the original matching edges internal to the blossom.
Why the Search Rules Work
Proof. Suppose instead that there is an augmenting path from the root \(r\) to an unmatched vertex. Read its edges from \(r\). The first edge is unmatched and leaves an \(S\)-vertex. Whenever the path reaches an unmatched vertex, rule 1 finds an augmenting path. Otherwise, an unmatched edge from a reached \(S\)-vertex either reaches an unlabelled matched vertex, which rule 2 labels \(T\) and then labels its matched partner \(S\), or reaches a labelled vertex. It cannot reach a labelled \(S\)-vertex without triggering rule 3, which would detect a blossom. A labelled \(T\)-vertex is already reached; its matching edge is its unique matching edge, and the next edge of the alternating path, if present, is unmatched and is scanned from its matched partner, labelled \(S\). Following the path in this way either finds its unmatched endpoint or detects a blossom. Both contradict the assumed exhausted search with neither event. Therefore no such augmenting path exists. \(\square\)
Contraction is justified by the blossom contraction-and-expansion result from the earlier material on contracting and expanding a blossom: contracting a blossom preserves whether an augmenting path from the search root exists, and an augmenting path found after contraction can be expanded to one before contraction. In applying that result, the matching in the contracted graph is the inherited matching described above. The base update is essential: it is the vertex through which the alternating structure outside the blossom attaches to the contracted vertex.
Proof. Each edge scan either adds labels, returns a path, detects a blossom, or requires no change. There are finitely many vertices and edges, so a scan on a fixed contracted graph cannot add labels indefinitely; once all eligible edges have been scanned, it is exhausted. Each contraction reduces the number of vertices by at least two, because a blossom is an odd cycle with at least three vertices. Thus only finitely many contractions can occur. If the search returns a path, the recorded contractions can be expanded to obtain an augmenting path in the original graph, by the contraction-and-expansion result stated above. If it terminates without returning a path, the lemma rules out an augmenting path in the final graph, and that same result rules one out in the original graph from the root. \(\square\)
Worked Searches
Worked Example: Detecting and Contracting a Blossom
Let \(V=\{r,x,y,z,w,t\}\), \(E=\{rx,xy,rz,zw,yw,wt\}\), and \(M=\{xy,zw\}\). Start at the unmatched root \(r\). Scan the edges from \(r\) in the order \(rx,rz\), then scan \(S\)-vertices in the order they enter the search.
| Step | Action | Labels or tree edges afterward |
|---|---|---|
| 1 | Start at \(r\). | \(S=\{r\}\); tree has no edges. |
| 2 | Scan \(rx\), which is outside \(M\); \(x\) is matched to \(y\). | Add \(rx\) and \(xy\); \(x\) is \(T\), \(y\) is \(S\). |
| 3 | Scan \(rz\), which is outside \(M\); \(z\) is matched to \(w\). | Add \(rz\) and \(zw\); \(z\) is \(T\), \(w\) is \(S\). |
| 4 | Scan \(yw\), outside \(M\), joining two \(S\)-vertices. | Their lowest common ancestor is \(r\); detect and contract the blossom. |
The tree paths from \(r\) to \(y\) and \(w\) are \(r,x,y\) and \(r,z,w\). Together with \(yw\), they form the odd cycle \(r,x,y,w,z,r\), of length \(5\). Its matching edges are \(xy\) and \(zw\); its other three edges are outside \(M\). Contract the blossom to \(B\). The edge \(wt\) becomes \(Bt\), and the inherited matching has no edge incident with \(B\), since the base \(r\) was unmatched. Thus \(B\) is an unmatched root, and \(t\) is unmatched.
Scanning \(Bt\) finds an augmenting path in the contracted graph. Expand it using the branch \(r,z,w\) of the blossom: the original path is \(r,z,w,t\). Its edges are \(rz\notin M\), \(zw\in M\), and \(wt\notin M\), so it is alternating and has unmatched endpoints. Check: replacing \(zw\) by \(rz\) and \(wt\) changes the matching from \(\{xy,zw\}\) to \(\{xy,rz,wt\}\), a matching of size \(3\).
Worked Example: Finding a Path Without a Blossom
Let \(V=\{r,a,b,c\}\), \(E=\{ra,ab,bc\}\), and \(M=\{ab\}\). Start from the unmatched vertex \(r\).
| Step | Action | Search state |
|---|---|---|
| 1 | Label the root. | \(r\) is \(S\). |
| 2 | Scan \(ra\notin M\). | Label \(a\) as \(T\); its matched partner \(b\) becomes \(S\). |
| 3 | Scan \(bc\notin M\) from \(b\). | \(c\) is unmatched, so return \(r,a,b,c\). |
The path edges are \(ra\notin M\), \(ab\in M\), and \(bc\notin M\). The matching after augmentation is \(\{ra,bc\}\), of size \(2\). Check: the two edges are disjoint and cover all four vertices, so the stated matching is valid and has one more edge than \(M\).
Worked Example: An Exhausted Search
Let \(V=\{r,a,b\}\), \(E=\{ra,ab\}\), and \(M=\{ab\}\). The only unmatched vertex is \(r\).
| Step | Action | Search state |
|---|---|---|
| 1 | Label \(r\) as \(S\). | \(S=\{r\}\). |
| 2 | Scan \(ra\notin M\). | Label \(a\) as \(T\); its matched partner \(b\) becomes \(S\). |
| 3 | Scan edges from \(b\). | Its only edge is \(ba\in M\), the parent edge; no new edge is available. |
The scan is exhausted, no blossom was found, and no unmatched endpoint was reached. The lemma therefore rules out an augmenting path from \(r\). Directly, the graph has only the two paths from \(r\) to its other vertices, and neither ends at an unmatched vertex: \(a\) and \(b\) are both matched. The matching \(\{ab\}\) has size \(1\), which is maximum because the graph has only three vertices and a matching cannot contain two disjoint edges.
Common Mistake and Practical Significance
Mistake: treating every edge to a labelled vertex as irrelevant. In the first example, after \(y\) and \(w\) are labelled \(S\), the edge \(yw\) is not a harmless duplicate discovery. Ignoring it and declaring the scan complete would miss the blossom and could miss the augmenting path exposed by contraction. The correction is to distinguish the labels: an edge from \(S\) to \(T\) needs no new label, but an edge from \(S\) to \(S\) triggers a base search and blossom contraction.
Edmonds’ search makes the alternating-path method usable in general graphs, where odd cycles prevent a direct bipartite-style search. Its output is either an augmenting path, which can be used to increase the matching, or an exhausted search that rules out such a path from the chosen root. To search for any augmenting path, run the procedure from the unmatched roots; after an augmentation, the matching changes, so a new search is made for the updated matching.
Check Your Understanding
For each question, use the search rules and state which edges belong to the matching.
- Why is the base of a blossom the lowest common ancestor of its two \(S\)-vertices?
- In a rooted alternating tree, what labels must the endpoints have for a scanned unmatched edge to trigger blossom contraction?
- For \(V=\{r,a,b,c\}\), \(E=\{ra,ab,bc\}\), and \(M=\{ab\}\), list the labels just before the search returns its path.
- Why does contracting a blossom reduce the number of vertices, even when the blossom is nested inside an earlier contraction?
- What conclusion follows when an edge scan is exhausted after all recorded blossoms have been contracted and expanded as needed?