Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.