How would we prove that if M is a matching in a bipartite graph which is not the largest possible, then there exists an M-augmenting path?
So I began by considering a matching larger than $M$ such that it would be the largest possible. However, I was a little confused here with regards to how I would bring about the values for the degrees of the different vertices and any potential paths through them. I know that the first vertex must be unmatched but I am not entirely sure on how to find/prove it.
Any help?
Let $M'$ be a maximum matching. Consider the symmetric difference $M\Delta M'$. The degree of a vertex in a symmetric difference of two matchings is at most two and hence each component of $M\Delta M'$ is a path or cycle. There must be a component with more edges from $M'$. Such a component must be a path and thus begins with a $M'$ edge and ends with $M'$ edge and is alternating. This is the augmenting path we seek.