I am reading "Data Structures and Algorithms" by Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman.
The key observation is that $M$ is a maximal matching if and only if there is no augmenting path relative to $M$. This observation is the basis of our maximal matching algorithm.
Suppose $M$ and $N$ are matchings with $|M| < |N|$. ( $|M|$ denotes the number of edges in $M$.) To see that $M \oplus N$ contains an augmenting path relative to $M$ consider the graph $G^{'} = (V, M \oplus N)$. Since $M$ and $N$ are both matchings, each vertex of $V$ is an endpoint of at most one edge from $M$ and an endpoint of at most one edge from $N$. Thus each connected component of $G^{'}$ forms a simple path (possibly a cycle) with edges alternating between $M$ and $N$. Each path that is not a cycle is either an augmenting path relative to $M$ or an augmenting path relative to $N$ depending on whether it has more edges from $N$ or from $M$.
…
I cannot understand the above proof of a proposition about maximum matching.
(By the way, I don't know why the authors use the word maximal instead of maximum.)
The authors wrote "Each path that is not a cycle is either an augmenting path relative to $M$ or an augmenting path relative to $N$ depending on whether it has more edges from $N$ or from $M$.".
I think this is not correct.
I think the following is correct:
"Each path that is not a cycle is either an augmenting path relative to $M$ or an augmenting path relative to $N$ depending on whether it has more edges from $N$ or from $M$ or an even length simple path with edges alternating between $M$ and $N$ .".
Am I wrong or right?
Best Answer
I think you are right: there could also be paths with the same number of edges in each, which are not augmenting paths. However, the fact that $|M|<|N|$ still means that there is at least one path with more edges from $N$ than from $M$ (cycles must have the same number of each) and hence there is an augmenting path for $M$.
Incidentally, the normal distinction between "maximum matching" and "maximal matching" is that a "maximum matching" is one of the largest possible size, whereas a "maximal matching" is one that can't be extended by adding an edge. In this sense, however, they are using the wrong word since they are clearly talking about maximum matchings.