Let's consider this graph:
Now I take a matching M that only contains the edge 1. Clearly this matching is not maximum, because I can take the edge 3, so given that:
We can easily notice that if there exists an augmenting path p with respect to M, then M is not maximum.
I should find an augmenting path w.r.t M. Looking at the definition for a matching M:
An augmenting path is an alternating path that starts from and ends on free vertices.
an alternating path is a path in which the edges belong alternatively to the matching and not to the matching,
What I don't get is how to build such a path given my matching? My only possibilites are:
- start from the top vertex of the edge 2
- start from the right vertex of the edge 5
- start from the bottom vertex of the edge 4
Now from there I take the edge 2 or 4 or 5, then I take the edge 1 and then I cannot go further.
So is the first quote a one-way implication (so if M is not a maximum matching then I don't always find an augmenting path)? Or did I misunderstood how to build my augmenting path?