Definition for alternating paths and augmented paths of a matching in a graph is defined as follows:
Given a matching M, an alternating path is a path in which the edges
belong alternatively to the matching and not to the matching. an
augmenting path is an alternating path that starts from and ends on
free (unmatched) vertices.
I think both concepts are not required to include all the edges of the matching. So from any alternating path, we can find a part of it which can be an augmenting path. But this would contradict a theorem that a matching is maximum if and only if there is no augmented path for it. So I wonder how I should understand the two concepts?
Thanks!
Best Answer
An alternating path is not required to include all edges of a matching. This causes no contradiction in the theorem you're citing: given a matching and an augmenting path, you can always create a matching with more edges. The simplest case is when the augmenting path is an edge that joins two vertices, neither covered by an edge of the matching, when you can just add the the extra edge (of the augmenting path).