Odd Cycles and Blossoms

Odd Cycles in Matching Searches

In a graph with a matching, every vertex is either matched to one other vertex or is unmatched. An alternating path switches between edges in the matching and edges outside it. In a bipartite graph, the two parts help organize searches for such paths. In a general graph, an odd cycle can disrupt that parity-based organization: two different routes around the cycle can have different lengths and therefore different alternating-edge patterns.

A matching \(M\) in a finite simple graph \(G=(V,E)\) is a set of pairwise vertex-disjoint edges. A vertex incident with an edge of \(M\) is matched; otherwise it is unmatched (or exposed). A path is alternating with respect to \(M\) if its edges successively lie outside and inside \(M\), or successively lie inside and outside \(M\). An augmenting path is an alternating path whose endpoints are unmatched and whose first and last edges are outside \(M\). For a path of positive length, switching its edges from outside \(M\) to inside \(M\), and vice versa, increases the size of the matching by one.

An odd cycle is not automatically a blossom. Its edges must have a particular pattern relative to the matching, including a specified base. Requiring the right pattern after the base is removed is essential: without it, an odd cycle with no matched edges could be incorrectly labelled a blossom.

Definition and Parity Pattern

If \(C\) has length \(2k+1\), then \(k\geq 1\). Deleting \(b\) leaves a path of length \(2k-1\), not \(2k\): the cycle has \(2k+1\) edges, and the two edges incident with \(b\) are removed. The path has \(k\) edges in \(M\) and \(k-1\) outside \(M\), with a matched edge at each end. Adding back the two edges at \(b\), both outside \(M\), gives \(k\) matched and \(k+1\) unmatched edges on the cycle.

Proof. Fix a blossom \(C\) with base \(b\), and delete \(b\) and its two incident cycle edges. The remaining path has \(2k-1\) edges, begins and ends with matched edges, and alternates. Its edge sequence therefore consists of \(k\) matched edges separated by \(k-1\) unmatched edges. The two removed edges are both unmatched, so \(C\) has \(k\) matched edges and \(k+1\) unmatched edges. Along the remaining path, no two consecutive edges are both unmatched: every unmatched edge is between matched edges. At either end of the path, its end edge is matched, so the adjacent edge at \(b\) is not part of a second consecutive-unmatched pair. The two edges at \(b\), however, are consecutive on the cycle and both unmatched. Thus \(b\) is the unique vertex where consecutive cycle edges are both unmatched, proving that the base is unique. \(\square\)

There is a related parity obstruction. An odd cycle cannot alternate between matched and unmatched edges at every pair of consecutive edges, including the pair where the cycle closes. The reason is that alternation along a linear listing of its edges forces the first and last edges to have the same status, while those two edges are consecutive at the starting vertex and would need opposite statuses to alternate around the cycle.

Proof. List the edges of a cycle of length \(2k+1\) in cyclic order as \(e_0,e_1,\ldots,e_{2k}\). If successive edges alternate along the list, each of the \(2k\) transitions from \(e_0\) to \(e_{2k}\) changes the edge status. An even number of changes leaves the status unchanged, so \(e_0\) and \(e_{2k}\) have the same status. But these two edges meet at the starting vertex and are consecutive around the cycle. To alternate at that closing pair, they would have to have opposite statuses. This contradiction proves the lemma. \(\square\)

A blossom gives the characteristic way this obstruction appears: the cycle alternates along the path left after deleting the base, but the two unmatched edges at the base meet consecutively. The definition records that precise pattern; it does not label every odd cycle a blossom.

Worked Examples

Why the Base Matters in a Search

In an alternating-path search, reaching vertices by paths of even or odd length helps determine which matching status an outgoing edge can have. An odd cycle can connect two routes that do not fit into one consistent parity pattern. In a blossom, the base is the specific vertex where the two unmatched cycle edges meet; the rest of the cycle, after removing the base, has the required alternating pattern. Keeping these features together lets a search recognize the odd-cycle structure instead of treating its two routes as though they had the same parity.

The examples also show why it is important to check the matching, not only the graph. The same triangle is a blossom for \(M=\{23\}\) with base \(1\), but it is not a blossom for \(M=\varnothing\). “Odd cycle” describes the graph structure; “blossom” describes that structure relative to a particular matching.

Common Pitfalls

Do not omit the end-edge condition. It is not enough that deleting a proposed base leaves an alternating path. The remaining path must start and end with matched edges. Otherwise the triangle with no matching would incorrectly qualify, since deleting any vertex leaves a one-edge alternating path, even though that edge is unmatched.

Do not reverse the parity argument. In a cycle of length \(2k+1\), the first and last edges in a linear listing are separated by \(2k\) transitions. If statuses alternate along those transitions, the first and last statuses are the same. Since these edges are consecutive at the starting vertex, that is precisely why they cannot alternate at the closing pair.

Do not infer that a blossom prevents augmentation. It complicates the parity logic of a direct search. As the example with vertices \(r,u,a,b,c,z\) shows, an augmenting path may still exist. Identifying the blossom is a structural step, not a conclusion that the matching is maximum.