The blossom algorithm is Edmonds' method for finding a maximum matching in a general graph. It works by contracting odd cycles, called blossoms, so the search for an augmenting path can continue.
The blossom algorithm is the standard Combinatorics method for finding a maximum matching in a general graph, especially when the graph is not bipartite. A maximum matching is the largest set of edges you can choose so that no two chosen edges share a vertex.
The part that makes the algorithm special is how it deals with odd cycles. In a simple matching search, an odd cycle can trap the search and make it look like no augmenting path exists. The blossom algorithm treats that odd cycle as a single contracted unit, called a blossom, so the search can move past the cycle instead of getting stuck on it.
That contraction step is the whole trick. You temporarily shrink the odd cycle into one super-vertex, search for an augmenting path in the smaller graph, and then expand the blossom again after the path is found. If the path uses the contracted blossom, the algorithm can translate that path back to the original graph and update the matching there.
This matters because augmenting paths are still the engine behind the method. An augmenting path is a path whose edges alternate between unmatched and matched edges, starting and ending at unmatched vertices. When you find one, you can flip the matched and unmatched edges along the path and increase the size of the matching by 1.
A common point of confusion is that a blossom is not just any cycle. It is an odd cycle that appears during the search for an augmenting path, often with a specific base vertex where the alternating-tree search meets itself. Even cycles do not create the same problem, because they do not block the alternating structure in the same way.
In class problems, you usually do not hand-run the full blossom algorithm unless the graph is tiny. More often, you are expected to recognize why a general graph is harder than a bipartite one, explain why odd cycles matter, or describe how contraction lets the matching search continue.
The blossom algorithm shows up whenever Combinatorics moves from clean bipartite matching problems into messy real graphs. Bipartite graphs have neat tools like Hall's Marriage Theorem and the Hopcroft-Karp algorithm, but those tools do not handle every graph. Once odd cycles appear, you need Edmonds' idea to keep the matching search moving.
This term also connects the theory of matchings to an actual algorithmic procedure. Instead of just saying, "Find the biggest matching," you get a concrete process: build an alternating forest, look for an augmenting path, contract any blossom that blocks the search, and repeat until no augmenting path remains. That is the kind of reasoning professors expect in graph theory and optimization problems.
It also helps explain why maximum matching is easier in some graphs than others. A lot of textbook examples look simple until one odd cycle changes everything. The blossom algorithm is the reason general-graph matching is still solvable efficiently instead of turning into a brute-force search over all edge sets.
In application problems, this idea models assignment and pairing situations where the relationship network is not neatly split into two groups. If you are matching workers to tasks, pairing devices, or designing a network, the graph may have cycles that make ordinary bipartite methods fail. Blossom is the tool that keeps the matching problem in the realm of exact optimization instead of guesswork.
Keep studying COMBINATORICS Unit 14
Visual cheatsheet
view gallerymaximum matching
The blossom algorithm is designed to find a maximum matching, so this is the outcome you are trying to reach. If you can identify the largest set of non-overlapping edges, you already know what the algorithm is optimizing for. Blossom is the method, maximum matching is the goal.
augmenting path
Blossom still depends on augmenting paths, just like simpler matching algorithms do. The difference is that blossom can contract an odd cycle when that cycle blocks the search. If you understand augmenting paths, the blossom algorithm makes more sense as a way to preserve that idea in harder graphs.
Hopcroft-Karp algorithm
Hopcroft-Karp is the fast matching algorithm for bipartite graphs, while blossom handles general graphs. They are often compared because both search for augmenting paths, but only blossom has to deal with odd cycles. If a problem says the graph is bipartite, blossom is usually not the tool you want.
Edmonds' Algorithm
Edmonds' Algorithm is the broader name commonly used for the blossom method. In many classes, the two terms point to the same idea: using blossom contraction to find a maximum matching in a general graph. If you see Edmonds' name, think matching in non-bipartite graphs.
A problem set question usually asks you to identify whether a graph needs the blossom algorithm or a bipartite matching method, then explain why. You may also be asked to trace an augmenting path, spot an odd cycle that becomes a blossom, or justify why contraction makes the matching search possible. On a quiz, the key move is naming the obstacle correctly: an odd cycle in a general graph. If the graph is bipartite, you should point toward Hopcroft-Karp instead. If it is not, blossom is the matching tool that fits.
These are both matching algorithms, but they solve different kinds of graphs. Hopcroft-Karp is for bipartite graphs, where the vertices split into two groups and odd cycles do not interfere the same way. The blossom algorithm is for general graphs and has to contract odd cycles to keep searching for an augmenting path.
The blossom algorithm finds a maximum matching in a general graph, not just a bipartite one.
Its main trick is contracting odd cycles, called blossoms, so the search for an augmenting path can continue.
When the algorithm finds an augmenting path, it can increase the matching by flipping matched and unmatched edges along that path.
If a graph is bipartite, you usually use a bipartite matching method instead of blossom.
Odd cycles are the feature that makes general-graph matching harder, and blossom is the method built to handle them.
The blossom algorithm is a method for finding a maximum matching in a general graph. It is famous for handling odd cycles by contracting them into a single blossom so the search for an augmenting path can keep going. That is what makes it useful beyond bipartite graphs.
It contracts odd cycles because those cycles can block the alternating-path search. Shrinking the cycle into one vertex lets the algorithm treat it like a simpler graph, find an augmenting path if one exists, and then expand the cycle again to update the matching in the original graph.
Hopcroft-Karp is built for bipartite graphs, while blossom works on general graphs. Both use augmenting paths, but blossom has the extra step of handling odd cycles. If the graph is not bipartite, Hopcroft-Karp is not enough.
Usually not for large graphs. In Combinatorics, you are more likely to explain the idea, identify when a graph needs it, or work through a tiny example that shows why an odd cycle must be contracted. The full algorithm is often more of a concept and method than a long hand computation.