Skip to main content
2 of 2
deleted 20 characters in body
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 is at even distance from the root. If $u$ is at odd distance from the root, I am not sure what to do. End fail.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187