# About a proof of a proposition about maximum matching (Aho, Hopcroft, Ullman)

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?

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$$.