Let G VE be a graph and M a matching on G Suppose G has no

Let G = (VE) be a graph and M a matching on G. Suppose G has no M-augmenting paths. Following the steps below to show that M is maximum. Let M\' be a maximum matching, and let H be the graph on V with edge set M delta M\', the symmetric difference of M and M\'. Show that for any v epsilon V, we have d_H{v) lesser than equal to 2. Observe that this implies that each connected component of H is either a path or a cycle. (You do not need to prove this observation.) Show that for each connected component C of H, the number of edges coming from M is at least the number of edges coming from M\'.

Solution

M is a maximum matching iff M admits no M-augmenting paths. Proof Suppose M has an augmenting path P = (a0, b1, a1, . . . , ak , bk+1) where ei = (ai1, bi) / M, 1 i k+1 and fi = (bi , ai) M, 1 i k. PSfrag replacements a0 a1 a2 b1 b2 b3 M0 = M {f1, f2, . . . , fk} + {e1, e2, . . . , ek+1}. 3 • |M0 | = |M| + 1. • M0 is a matching For x V let dM(x) denote the degree of x in matching M, So dM(x) is 0 or 1. dM0(x) = dM(x) x 6 {a0, b1, . . . , bk+1} dM(x) x {b1, . . . , ak} dM(x) + 1 x {a0, bk+1} So if M has an augmenting path it is not maximum. 4 Suppose M is not a maximum matching and |M0 | > |M|. Consider H = G[MM0 ] where MM0 = (M \\ M0) (M0 \\ M) is the set of edges in exactly one of M, M0 . Maximum degree of H is 2, at most 1 edge from M or M0 . So H is a collection of vertex disjoint alternating paths and cycles.

|M0 | > |M| implies that there is at least one path of type (d). Such a path is M-augmenting