Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.