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) and in Alexander Schrijver's Combinatorial Optimization: Polyhedra and Efficiency (proof of Theorem 24.7).

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.

Schrijver's book seem to do the same but is more vague about how to get from an alternating path in $G$ to an alternating path in $G/B$ (he just regards this as evident in (24.21)).

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.

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.