# Finding the Augmenting Path

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.

-

## 1 Answer

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

-
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