Hello all,

I've been studying this topic lately, and I came out with a question which answer I have not been able to find anywhere.

I know very well the history about Edmonds' Blossom algorithm, however, it is well known that a given matching is the maximum one if no more augmenting paths can be found on the graph. So, my question is the following one:

I implemented a simple DFS algorithm that tries to find an augmenting path, and if found, it makes the flip we all know and adds/removes the flipped edges to the matching. In my DFS I only mark nodes that are reached in even levels (i.e. nodes found after following a matched edge, plus the first unmatched node) as visited, furthermore I also care about the nodes in the active path so as to avoid stepping in the same node and generating cycles. So, why this does not work? of course the reason is because there are augmenting paths my algorithm cannot find, but why?

All of this converges to a simple question: why in Edmonds' algorithm is it necessary to shrink blossoms? I've read many papers where it is explained how to shrink blossoms and why an augmenting path in the reduced graph is still valid in the expanded one, but they never explain why this is actually necessary!

Thanks for your help.