Let's consider this graph:

enter image description here

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?


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.

  • $\begingroup$ I know how to find the maximum matchings in this graph. My question is, given the matching I started with, which I know that it's not a maximum matching, how can I find an augmenting path w.r.t this matching? Sorry maybe the title of the question is a bit misleading but I think it's enough clear in the body ;) $\endgroup$ – user2336315 May 22 '15 at 19:07
  • $\begingroup$ Ah, indeed! Let's see. $\endgroup$ – prime4567 May 22 '15 at 19:15
  • $\begingroup$ A path is a sequence of edges that connects the vertices, so I'm not sure 3,1,4 and 3,1,5 are paths since the vertices from 3 are not connected with the one from 1-4 or 1-5. $\endgroup$ – user2336315 May 22 '15 at 19:40
  • $\begingroup$ I think I got it. I think the trick is in the fact that you traverse 1 back and forth in one alternation. This is an undirected graph so given an edge with vertices a and b the edge is just {a,b}, no? Unlike in a directed graph where they would be distinct, i.e. (a,b) or (b,a). So the trick is that you go up the edge 1 and down again BUT that counts as a single alternation. I hope that was clear? So the augmented path starts with edge 2, then 1(going up), then 1(going back down), and then edge 4 (or 5 for another path). $\endgroup$ – prime4567 May 22 '15 at 20:07
  • $\begingroup$ But 2-1-5 and 2-1-4 are not paths. The vertices need to be distincts (except the first and the last and then you get a cycle)... If I follow the vertices from your "path", I get two times on the bottom vertice of the edge 1 and that is not my starting/end point so it's not a path. $\endgroup$ – user2336315 May 22 '15 at 20:10

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.