Reading a Blossom Search Trace
Edmonds’ blossom search finds augmenting paths in general graphs by growing an alternating forest. When the search encounters an odd cycle in the forest, it contracts that cycle to a single vertex, continues the search, and later expands the cycle to recover a path in the original graph. The purpose here is to make those operations explicit: which vertices receive labels, what triggers a contraction, and how the final path is lifted.
Throughout, graphs are finite, undirected and simple. A matching \(M\) is a set of edges no two of which share an endpoint. A vertex not incident with an edge of \(M\) is exposed. An augmenting path for \(M\) is a path whose edges alternate between edges outside \(M\) and edges in \(M\), and whose two endpoints are exposed. Augmenting along the path means deleting its matching edges from \(M\) and adding its other edges.
For a single-root search, the forest is built as follows. Scan edges incident with outer vertices. If an edge from an outer vertex reaches an unlabelled vertex, label that vertex \(T\); if it is matched, its matching partner is labelled \(S\) and added to the tree. If the reached vertex is exposed, the search has found an augmenting path. If an edge joins two outer vertices in the same tree, record the blossom and contract it. Edges joining vertices already in the same blossom, and the matching edge from an outer vertex to its inner parent, do not add new forest vertices.
The labels encode alternation: each step from an outer vertex to a newly labelled inner vertex uses an edge outside \(M\), and the next step from that inner vertex to its matched partner uses an edge in \(M\). Thus an outer vertex has an even-length alternating tree path from the root, while an inner vertex has an odd-length one. This is the invariant maintained as the forest grows.
Why the label rule is consistent. Initially the root is exposed and has a length-zero path. When an outer vertex reaches an unlabelled vertex by an edge outside \(M\), the new path has one more, unmatched edge, so the new vertex is inner. If that vertex is matched, its unique matching edge extends the path by a matched edge to its partner, which is outer. These two steps preserve alternation and the stated parity. Contraction treats a blossom as one outer vertex; expanding it uses one of the alternating routes through its odd cycle. The earlier material on contracting and expanding a blossom establishes that this preserves the existence of augmenting paths. Once a path is found, the earlier correctness result on blossom augmentation justifies flipping its edges.
Worked Example: Contract, Search, and Lift
Worked Example: Contract, Search, and Lift
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,13,23,24,45,56\}\). Take the matching \(M=\{23,45\}\). The exposed vertices are \(1\) and \(6\). Run a single-root search from \(1\), scanning the listed edges in the order used below.
| Step | Edge or action | Forest labels and result |
|---|---|---|
| 1 | Start at \(1\) | \(1:S\), the root |
| 2 | Scan \(12\) | \(2:T\); its matched partner \(3\) is added as \(3:S\) |
| 3 | Scan \(13\) | \(1\) and \(3\) are outer vertices in the same tree; detect a blossom |
| 4 | Contract \(\{1,2,3\}\) to \(B\) | \(B:S\), with base \(1\) |
| 5 | Scan the contracted edge \(B4\), represented by \(24\) | \(4:T\); its matched partner \(5\) is added as \(5:S\) |
| 6 | Scan \(56\) | \(6\) is exposed, so an augmenting path is found |
To verify the blossom, the tree paths from the common ancestor \(1\) to the two outer endpoints are \(1\) and \(1,2,3\). Together with edge \(13\), these form the cycle \(1,2,3,1\). It has length \(3\), and its base is \(1\). The matching edge on this cycle is \(23\).
In the contracted graph, the search path is \(B,4,5,6\). Its edges have the pattern unmatched, matched, unmatched: \(B4\) represents the unmatched edge \(24\), \(45\) is in \(M\), and \(56\) is outside \(M\). To lift this path, the attachment to \(4\) is at vertex \(2\) of the blossom. Use the even-length route \(1,3,2\) from the base \(1\) to \(2\). The lifted path is therefore \(1,3,2,4,5,6\).
Check each edge of the lifted path in order: \(13\notin M\), \(32=23\in M\), \(24\notin M\), \(45\in M\), and \(56\notin M\). The endpoints \(1\) and \(6\) are exposed, so this is an augmenting path. Flipping its edges removes \(23\) and \(45\), and adds \(13\), \(24\), and \(56\). Thus the new matching is \(M'=\{13,24,56\}\).
Check: the three edges in \(M'\) have disjoint endpoints and cover all six vertices. Hence \(M'\) is a perfect matching. No matching on six vertices can have more than \(6/2=3\) edges, so the size-three result is maximum. Independently, the path has five edges, with three outside \(M\) and two in \(M\), so flipping increases the matching size by \(3-2=1\), from \(2\) to \(3\).
Worked Example: Augmentation Without a Blossom
Worked Example: Augmentation Without a Blossom
Let \(G=(V,E)\), where \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\). Let \(M=\{bc\}\), so \(a\) and \(d\) are exposed. Search from \(a\), scanning edges in the order \(ab,bc,cd\).
| Step | Action | Labels or path |
|---|---|---|
| 1 | Begin at \(a\) | \(a:S\) |
| 2 | Scan \(ab\) | \(b:T\); its matching partner \(c\) becomes \(c:S\) |
| 3 | Scan \(cd\) | \(d\) is exposed; the path \(a,b,c,d\) is found |
The path edges are \(ab\notin M\), \(bc\in M\), and \(cd\notin M\). Flipping gives \(M'=\{ab,cd\}\). These two edges are disjoint, and together they cover all four vertices. Since a matching on four vertices has at most \(4/2=2\) edges, this matching is maximum. In this trace every new outer vertex is reached through its matching edge, and no edge joins two outer vertices in the same tree, so no blossom is contracted.
Worked Example: A Blossom with No Exit
Worked Example: A Blossom with No Exit
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,23\}\). The vertex \(4\) is isolated. Take \(M=\{23\}\) and search from exposed vertex \(1\). Scanning \(12\) labels \(2:T\) and its matched partner \(3:S\). Scanning \(13\) now finds an edge between the outer vertices \(1\) and \(3\) in the same tree.
The detected blossom is the triangle \(1,2,3,1\), with base \(1\). Contract it to a single outer vertex \(B\). There is no edge from \(B\) to any vertex outside the triangle, so the search from this root has no further edge to scan and finds no augmenting path. The other exposed vertex \(4\) is isolated, so a search rooted there also has no edge to scan.
Check: the only edges of \(G\) are the three edges of a triangle. Any two of them share a vertex, so a matching can contain at most one edge. The given matching has one edge and is therefore maximum. This trace shows why finding a blossom is not itself finding an augmenting path: contraction lets the search continue, but an exposed endpoint must still be reached.
How to Record and Check a Trace
A useful trace separates the search decisions from the final expansion. At each stage, record the current outer and inner vertices, the edge being scanned, and the reason for the action. When a blossom is found, also record its base, its cycle, and the original vertices represented by the contracted vertex. After an augmenting path is found in the contracted graph, expand each contracted blossom along a route that makes the lifted path alternate correctly.
Choose an exposed root and label it \(S\). Record the matching edges before searching.
From an \(S\)-vertex, use an unmatched edge to reach a new \(T\)-vertex, then follow its matching edge to a new \(S\)-vertex when it has a mate.
If its endpoints belong to the same tree, find their common ancestor, record the resulting odd cycle and contract it. If they belong to different trees, their tree paths and that edge give an augmenting path.
Lift any contracted path, check alternation and exposed endpoints in the original graph, then flip its edges and verify that the result is a matching.
A common mistake is to lift a contracted path through the shortest-looking route inside the blossom without checking parity. In the first example, using \(1,2\) to reach the attachment vertex \(2\) would give the sequence \(1,2,4,5,6\). Its first two edges, \(12\) and \(24\), are both outside \(M\), so it is not alternating. The correction is to use the other route around the blossom, \(1,3,2\): its edges are unmatched then matched, and the following edge \(24\) is unmatched. The lifted path \(1,3,2,4,5,6\) therefore alternates throughout.
Another important distinction is between a search trace from one root and a conclusion about the entire matching. Exhausting the forest from one exposed root shows only that this search did not find an augmenting path from that root. To report that a full search has exhausted all possibilities, every relevant exposed root must be handled according to the search procedure. In the isolated-vertex example, vertex \(4\) has no incident edge, so its separate search ends immediately.
Check Your Understanding
For each question, state the graph and matching information needed to justify your trace.
- In the first example, why does edge \(13\) identify a blossom with base \(1\), rather than an augmenting path?
- In the first example, list the matching status of every edge on the lifted path and verify that its endpoints are exposed before augmentation.
- For a search in which an outer vertex reaches an unlabelled matched vertex, explain why the reached vertex is labelled \(T\) and its matching partner \(S\).
- In the third example, why does contracting the triangle not create an augmenting path to vertex \(4\)?
- Explain why a route through a blossom must be checked for alternation even when it connects the correct attachment vertices.