Sequences

The fat edges in the graph G displayed in Figure 13.2 form a matching M. The vertices a, f, and y are exposed with respect to M, and the sequences (a, b, c, d, e, f) and (a, b, c, u, v,w, x, y) define augmenting paths P and, respectively. Interchanging the roles of edges and non-edges of M on the path yields the matching M_ of cardinality |M| + 1 exhibited in Figure 13.3; more formally, we replace M by M ⊕, where ⊕denotes the symmetric difference. Note that is a maximal matching of G, as there is only one exposed vertex.