# Finding the Augmenting Path

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.

-

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