Details

In the snapshots the graph has 18 vertices. The initial augmenting path is just the edge {1, 15}. At the next-to-last step the augmenting path is {8, 13, 5, 14, 4, 17}, and so the final maximum matching has the edges {8, 13}, {5, 14}, and {4, 17} added. The subsequent tree search fails, but the orange vertices in the tree—13, 14—together with the upper part of the graph with the uncolored vertices in the tree deleted—1, 2, 3, 4, 6, 7—define a vertex covering of size 8 that proves that the matching of size 8 is the largest possible.

Proofs of the facts stated here can be found in [1]. Similar problems can be formulated for weighted graphs, and a maximum-weight matching can be found by similar techniques (Kuhn–Munkres algorithm). And similar problems can be formulated for general graphs (not bipartite) and solved by an algorithm known as the Blossom algorithm due to J. Edmonds. That is more complicated than the relatively simple algorithm that handles the bipartite case; see [2].

[1] R. A. Brualdi, Introductory Combinatorics, fourth ed., Saddle River, N.J.: Pearson Prentice Hall, 2004.

[2] W. J. Cook, W. H. Cunningham, W. R Pulleyblank, and A. Schrijver, Combinatorial Optimization, New York: Wiley, 1998.