CSDS 455: Applied Graph Theory
Homework 2
For this assignment, you will need to read about bipartite matchings. Look up the Hopcroft-Karp Algorithm
for finding a bipartite matching.
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
.
