How does this algorithmic proof of Edmonds-Gallai work?

Question

Sorry, this is going to be technical and dirty. I am not looking for a proof of the Edmonds-Gallai structure theorem (I understand two of them, even if they are rather similar); I am trying to understand a particular one (and wondering if it is subtly wrong).

The proof I am talking about is in Lecture 3 of Michel Goemans' 18.438 (2009) (warning: these are scribe notes written by students).

In Lecture 3, the argument I fail to understand is between Corollary 4 and Claim 5. The argument is supposed to show the following fact: If $G$ is a graph, $M$ is a maximal matching of $G$, $v$ is a vertex of $G$, $X$ is the set of vertices of $G$ unmatched by $M$, and $B$ is an $M$-blossom of $G$ (as far as I understand, this means a blossom of any flower, not necessarily of a flower with empty stem), then, given an alternating path from $X$ to $v$ in $G$, we can find an alternating path from $X$ to $v$ in $G/B$ (the graph $G$ after shrinking the blossom $B$) whose length has the same parity as the length of the original path. Here is how this is proven in the notes:

"Conversely, if we have an alternating path $P$ in $G$ from $X$ to a vertex $v$ which intersects a blossom $B$ then consider the first time $P$ visits a vertex of the corresponding flower. We can now replace the this prefix of $P$ with part of the flower in such a way that we still have an alternating path and the parity of the length of the path has not changed."

I don't understand why this works when the path $P$, after it visits a vertex of the flower for the first time, decides to stray away from it but later comes back to its stem, strays again, then again revisits the flower at its blossom, etc.. In this case, if we do our prefix replacement, we can end up with a walk that has repeated vertices, thus no longer is a path.

I have tried some variations of this argument, with "last time" instead of "first time" and suffix replacement instead of prefix replacement. None of them seem to work in all cases.

Alexander Schrijver's book Combinatorial Optimization: Polyhedra and Efficiency (proof of Theorem 24.7) makes a similar argument, which however avoids these issues by considering only flowers with empty stem. The argument does work for such flowers, though, of course, it is not trivial that the problem can be reduced to this case.

As I said, I know other proofs of Edmonds-Gallai, but they are completely avoiding blossom-shrinking arguments and I think this one is different enough to be interesting in its own.

EDIT: Goemans has shown me a way to correct the proof. (It requires changing various parts of the proof to make it closer to Schrijver's.) I believe the question can be considered closed by now.

Answer 1

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.