A matching M in a graph G is maximum if and only if there is no M-augmenting path in G.
for each exposed vertex v
using BFS, search the alternating-path subgraph (starting from v, paths of the form edge-not-in-M, edge-in-M, edge-not-in-M, …)
if an odd cycle is found in this subgraph, then there must be two paths through this cycle that meet, so the first two edges of the cycle (measured by distance to v) must diverge, and so must be not-in-M. since the two forks of this path meet in the cycle, the cycle must have 2t+1 edges, and t of them must be in M. such a cycle is called a blossom. replace it with a single vertex, and continue the search for an augmenting path from v in the reduced graph.
if an augmenting path from v is found, find the corresponding augmenting path in the original graph by replacing the blossom.
graph G: V = { a b c d e v w x y } E = { vw wa ab bc cd de ea bx ey}
M = { wa ey bx cd }
from exposed v, alternating path subgraph has edges { vw wa ae ey ab bx }, no odd cycle found, (G,M) has no augmenting path from v
same G as above
M = { wa bc ed }
from exposed v, alternating path subgraph has edges { vw wa ab ae bc ed cd }, blossom abcde found, shrink, call new vertex a' = {a b c d e}, new graph G' = (V', E')
E'= { vw wa' a'x a'y }, M' = { wa' }, augmenting path P' = { v w a' x }
flipping edges on P' gives new matching M* = { vw a'x } in G'
M* yields new matching { vw bx cd ae } on original graph