Consider the following graph and matching (bold edges) on the graph.
Problem 1: For the above bipartite graph and given maximal matching (the bold edges), prove that it is possible for the Hopcroft-Karp Algorithm to produce such a matching at the end of one of the algorithm’s iterations.
Problem 2: Trace the remaining steps the Hopcroft-Karp algorithm will take, starting with the above matching, to produce a maximum matching for the graph. Be certain to identify the augmenting paths found by the algorithm.
Problem 3: Let M and N be different matchings in a bipartite graph G with |M| > |N|. Prove that there exist matchings M0 and N0 in G such that |M0| = |M| − 1 and |N0| = |N| + 1 and M ∪ N = M0 ∪ N0 and M ∩ N = M0 ∩ N0.
