# Maximum matching blossom algorithm

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf

Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just iteratively finding a augmenting path and complementing it. I am talking about edmond blossom algorithm.

this is what I was looking for in the first step we have only 13 edges and we can not find any augmenting path.

now due to bloosom contrast we have increased matching by 1 edge.

• Apparently the difficulty is finding augmenting paths in non-bipartite graphs. Do you have any algorithm in mind? – Yuval Filmus Apr 5 at 20:33
• This might run into problems if there are odd cycles. See for example Section 3 here: cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. – Yuval Filmus Apr 5 at 20:37
• The algorithm in Section 3 is only guaranteed to find an augmenting path in bipartite graphs. Perhaps you have a different algorithm in mind. – Yuval Filmus Apr 5 at 21:11
• It’s all in Section 3. Read it carefully. – Yuval Filmus Apr 5 at 21:21
• Edmonds’ algorithm finds a maximum matching in any graph. – Yuval Filmus Apr 6 at 7:38