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.

I had a question about a specific graph, (a) found here:

http://upload.wikimedia.org/wikipedia/commons/9/98/Maximum-matching-labels.svg

If I were to add an edge between the two leaves of the tree, this would mean that the newly added edge would be part of the maximum matching. However, I'm having a problem finding the augmenting path in this case. I know that a matching is only maximum iff there is no augmenting path, but I cannot find this augmenting path in this case.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The augmenting path in that case is the path consisting only of the edge you added.

share|improve this answer
    
So an augmenting path does not necessarily have to include a matched edge? –  jaskel Nov 22 '11 at 3:58
    
@jaskel: Correct. An augmenting path is simply an alternating path with respect to the matching, and a path of length one is a perfectly good alternating path. –  Zach Langley Nov 22 '11 at 4:01

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.