Skip to main content
1 of 2
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is another approach that fails for a different reason. Perhaps the two failures can be merged into success, but I have not thought about this too deeply.

It suffices to prove the claim for shrinking just one blossom. Now, we instead view the alternating path $P$ as starting from $v$ and let $u$ be the first vertex that it meets the flower with the blossom. Note that the edge right before it meets this flower must be a non-matching edge. Now if $u$ is in the blossom, then by proceeding backwards to the root of the flower, we get a path from $v$ to $X$ in the contracted graph. This is also true if $u$ is not in the blossom, unless $u$ happens to be adjacent to the root. In that case we cannot proceed backwards to the root. End fail.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187