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?
 A: 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.
A: 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.
A: 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.
