How to find a maximum matching in this graph

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?

Solution 1:

The algorithm you're looking for is called the Hungarian Maximum Matching Algorithm, and it works for any bipartite graph, for which it always gives the largest-size matching. More detailed info can be found on this Wolfram MathWorld page and this link has a neat visualisation of how the algorithm works.