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:
- The path has odd length (in terms of edges).
- Its ends are not covered by $M$.
- 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 1
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.