Given a collection of vertices that can be split into two groups (let’s say and ), we can define an edge to exist if is qualified for .

Then, a matching is a collection of edges between and such that each vertex appears in at most one edge of the matching. A perfect matching occurs if every vertex is matched.

We can ask a few Optimization questions:

  1. Given , does there exist a perfect matching?
  2. How fast can we find a perfect matching, if it exists?
  3. If there is not, what is the maximum cardinality of a perfect matching within this set of vertices and edges?

Hall’s theorem

Assume that is bipartite. Then the claim is that there exists a perfect matching if and only if two conditions are met: first, that , and second, that for any , it is true that , where is the set of all vertices that are neighbors of .

Maximum matching


Create a source vertex that leads into all the vertices in one partition, and a sink vertex that all vertices in the other partition lead to. Create edges from all vertices from one partition, to all vertices in the other. Set the capacity of all edges to 1. Then, run a Maximum flow algorithm.


  • With FF: runtime becomes
  • Capacity scaling:
  • EK:

What happened? Edmunds-Karp is supposed to be one of the fastest max flow algorithm, but it’s the slowest one here.


For EK, there are still stages and BFS still takes time. However, since all edges have capacity of 1, when we push flow on a path, all edges on the path are saturated. This means we create back edges every iteration. So, instead of max iterations, we actually have of them.

So we already have a speed up by just observing the nature of our bipartite graph.