Talk:Blossom algorithm

i think the definition of blossom here is slightly incorrect. a blossom is not just a cycle of size 2k+1 that contains exactly k matched edges. if it were that, then, contrary to the main theorem about blossoms, the following graph G would contain a blossom B and an augmenting path P even though after contracting B, the resulting graph G' does _not_ contain an augmenting path: a | b / \ c-d-e-f

(here the matching is M = {ab, de}, the fake blossom B = {bd, de, eb}, and the augmenting path P = {cd, de, ef}. G' after contracting B has no augmenting path.) rather, i think a blossom is also required to have connected to its base (b in this case) a simple path, vertex disjoint with B except for the base vertex, with an even number of edges, beginning with a free vertex, and alternating between unmatched and matched edges.

does anyone want to weigh in on this? --Unique-k-sat (talk) 05:49, 19 October 2009 (UTC)