Question: In Exercise, one of the connected components suggests a way to modify M2 by removing one or more edges and substituting one or more edges from M1 that will give you a larger matching M'2 related to M2. In particular, this larger matching should saturate everything M2 saturates and more. What is M'2 and what else does it saturate?
Exercise: In the graph G of Figure, let M1 be the matching {l, 1}, {s, 2}, {t, 4}, {m, 5}, {e, 6}, {b, 9}, {f, 8}, and let M2 be the matching {l, 4}, {s, 2} {t, 1}, {m, 6}, {e, 7} {b, 8}. Recall that for sets S1 and S2 the symmetric difference of S1 and S2, denoted by S1?S2 is (S1 ∪ S2) - (S1 ∩ S2). Compute the set M1 ? M2 and draw the graph with the same vertex set as G and edge set M1 ? M2. Use different colors or textures for the edges from M1 and M2 so you can see their interaction. Describe the kinds of graphs you see as connected components as succinctly as possible.
