# Edmond's Blossom algorithm explanation

Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph algorithm to construct a maximum matching in a graph (matching is a set of edges without any common vertex; maximum matching is a matching with the highest cardinality of this set).

I do understand the idea behind finding augmenting paths and reversing the matching on them to get a matching with one higher cardinality,

what I don't understand is why odd cycles are a problem in finding an augmenting path (the algorithm says to "shrink" any odd cycle found while searching for an augmenting path).

My best guess is that an odd cycle doesn't allow you to visit some path connected to the cycle because you come back along the same path that led you to the cycle? but I am not sure.

How does an odd cycle create a problem, but even cycle doesn't?

A simple visual description, if someone can provide, might also be helpful.

Also, is this question suitable for this site or should I ask it on CS stackexchange instead?

When looking for an augmenting path $$P$$, we are looking for a set of edges which we can with some edges in the current matching $$M$$ to hopefully obtain some bigger matching $$M'$$. In particular, along an alternating path $$P$$ the edges alternate between being in $$M$$ and being in $$M'$$. Now suppose this augmenting path $$P$$ is in fact an odd cycle. By definition a matching cannot contain two adjacent edges. However, note that since $$P$$ is an odd cycle and the edges along $$P$$ alternate between being in $$M$$ and being in $$M'$$, then $$P$$ must contain two adjacent edges from $$M$$ or two adjacent edges from $$M$$ (draw out some examples to see this). Thus we cannot swap edges on an augmenting path which is an odd cycle to obtain a bigger matching, and so instead we keep the edges in $$M$$ which are in this odd cycle. In other words, we are not interested in the odd cycle augmenting paths since we cannot obtain a bigger matching from them.