Theorem 5.25: Mis a maximal matching of G iff there is no augmenting path relative to M. Proof:(1) There is no augmenting path relative to M, we prove m is a maximal matching ofG Suppose m andn are matching with MN To see that men contains an augmenting path relative to M we consider G=(V, MEN) l≤dc;(v)≤2 Since mn, men has more edges from N than M and hence has at least one augmenting path relative to M contradiction▪ Theorem 5.25：M is a maximal matching of G iff there is no augmenting path relative to M. ▪ Proof: (1) There is no augmenting path relative to M, we prove M is a maximal matching of G . ▪ Suppose M and N are matching with |M|<|N|. ▪ To see that MN contains an augmenting path relative to M we consider G’ = (V’, MN ) ▪ 1≤dG’(v)≤2 ▪ Since |M|<|N|, MN has more edges from N than M and hence has at least one augmenting path relative to M ▪ contradiction