# Concept of M-augmenting path to find a larger matching than $M$

I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $$M$$ and describes a path $$P$$ that is $$M$$-augmenting if:

1. The path has odd length (in terms of edges).
2. Its ends are not covered by $$M$$.
3. Its edges are alternately out of and in $$M$$.

Theorem 16.1 then states that we either have a matching of maximal size or an augmenting path exists.

I don't understand this statement. See the graph below for example. For now, we have the edge between vertices 2 and 5 in a matching $$M$$. I can't find any path that satisfies the three conditions above. Yet, this is obviously not a maximal matching since the edge between vertices 1 and 4 can be added to increase its size. What am I missing and why is my understanding so way off?

Further, if I'd used 1-4 as my initial matching, it would have been impossible to find a path that satisfies condition 2. Conversely, I take the graph the the author himself provides as an example of an augmenting path. In the simple linear graph below (which is also a linked list), an augmenting path satisfying the three conditions above exists. However, where is the edge that can be added to this graph to increase the size of $$M$$? ## 1 Answer

Actually, I realized what I was missing shortly after posting the question and squinting at the pictures again. Instead of deleting, figured I'd simply post the answer for future reference. The thing I was missing was that the new matching won't have the same edges as the original matching. In the first figure, 3->5->2->4 is such a path and 2->4 $$\cup$$ 3->5 becomes a larger matching.