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

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

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|cite|improve this question
up vote 1 down vote accepted

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

share|cite|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


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.