How to find a maximum matching in this graph

Question

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.

and

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?

Answer 1

Looks like there are 4 maximal matchings:{3,1}, {3,4}, {3,5}, {2}. They're matchings, since they do not share any vertices, and they're maximal since by adding any additional edge (to any of those four) necessitates the existence of a shared vertex, thereby rendering them as non-matchings.

Answer 2

If you have the matching formed from just edge 1, then edge 3 by itself is an augmenting path:

• its endpoints are unmatched, and
• the edges (vacuously) alternate between matched and unmatched edges.

There’s no requirement in an alternating path that the path actually use both matched and unmatched edges.

Once you’ve found that augmenting path, you can then add edge 3 into your matching to produce a larger matching.