# Do alternating and augmented paths for a matching need to cover all the edges in the matching?

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!

-

## 2 Answers

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).

-

Unfortunately most of the definitions are somewhat confusing and ambiguous in that they never assert that an extreme case of alternating matched and unmatched edges can be a single un-matched edge as an augmenting path. So is the case when a bipartite graph having exactly one perfect matching, how one should proceed.

-