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

.