Concept of M-augmenting path to find a larger matching than $M$
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-&gt;5-&gt;2-&gt;4 is such a path and 2-&gt;4 $\cup$ 3-&gt;5 becomes a larger matching.