1
$\begingroup$

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 Answers 1

1

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

  • 0
    @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.2011-11-22