Given a matching, a $M$-augmenting path is a path that alternates between edges in $M$ and edges not in $M$ where endpoints are unmatched.

Can a $M$-augmenting path consist of three vertices along with two unmatched edges? (Think: $K_{1,2}$)


No, it can't. We can in fact say something more precise about the structure of augmenting paths: an $M$-augmenting paths is a path that alternates between edges in $M$ and edges not in $M$ where only the endpoint are unmatched.

The idea is that we construct an augmenting path by starting at an unmatched vertex, and building until we get to another unmatched vertex. So, in your example, if we started with an unmatched vertex $v_1$ and took an edge (which is, by assumption, not in $M$) to get to another unmatched vertex $v_2$, we'd stop there! That's the simplest kind of $M$-augmenting path: an edge between two unmatched vertices, which we can just add to our matching.

The only reason we'd keep going is if the second vertex $v_2$ were matched to something. Then we extend the path by going to $v_3$, the vertex such that $v_2 v_3 \in M$, and keep going from there. This also does not produce a path of two unmatched edges.

  • $\begingroup$ Thanks. If you have access to youtube, youtube.com/watch?v=C9c8zEZXboA, at 1:45 mark, the person talks about T-to-R path being an M-augmenting path, even though no other path connecting a vertex reachable from T contains an alternating path. Is this the same as what you are talking about? $\endgroup$ – Olórin Oct 3 '17 at 2:10
  • $\begingroup$ Exactly. If the path gets any longer, it's only by being alternating. $\endgroup$ – Misha Lavrov Oct 3 '17 at 2:18

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.