u3 U2 M={{vl,ul},{v2,u2},{v3,u3} M is a complete matching from Vi to v2, but it is not a complete matching from v2 to V1
▪ M={{v1,u1},{v2,u2},{v3,u3}} ▪ M is a complete matching from V1 to V2, but it is not a complete matching from V2 to V1
Definition 39: Given a matching M in a graph G, a M-alternating path(cycle) is a path(cycle) in g whose edges are alternately in m and outside ofm(i.e. if an edge of the path is in M, the next edge is outside M and vice versa). A M alternating path whose end vertices are M unsaturated is called an M-augmenting path. 2 vO y y
▪ Definition 39: Given a matching M in a graph G, a M-alternating path (cycle) is a path (cycle) in G whose edges are alternately in M and outside of M (i.e. if an edge of the path is in M, the next edge is outside M and vice versa). A Malternating path whose end vertices are Munsaturated is called an M-augmenting path
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 MN contains an augmenting path relative to M we consider G’ = (V’, MN ) ▪ 1≤dG’(v)≤2 ▪ Since |M|<|N|, MN has more edges from N than M and hence has at least one augmenting path relative to M ▪ contradiction