Can a $M$-augmenting path consist of three vertices along with two unmatched edges?

Question

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}$)

Answer 1

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.