(2)If M is a maximal matching of G then there is no augmenting path relative to M Assume that there exists an M-augmenting path To see that Mep is a matching of g and MOpIMI IMOp is a matching of g Vel, e2EMOp, el and e2 are not adjacent 2)M⊕p|>M MOpMMU p)- Mnp=MU pl-Mnpl M+p-2 Mnp) =|MH+1▪ (2)If M is a maximal matching of G then there is no augmenting path relative to M ▪ Assume that there exists an M-augmenting path p. ▪ To see that Mp is a matching of G and |Mp|>|M| ▪ 1)Mp is a matching of G ▪ e1,e2Mp, e1 and e2 are not adjacent. ▪ 2) |Mp|>|M| ▪ |Mp|=|(M∪p)-(M∩p)|= |(M∪p)|-|(M∩p)| ▪ =|M|+|p|-2|(M∩p)| ▪ =|M|+1