A matching is a subset of such that no two edges share a vertex, i.e. for any two edges we have .
A perfect matching is a matching that meets every vertex of , i.e. for every there is an edge .
Problem: Given a bipartite graph we wish to know whether has a perfect matching. Note that the yes answer has a short certificate, namely the perfect matching itself. The certificate for the no answer follows from Hall’s theorem which we give below.
Hall’s Theorem: has a perfect matching if and only if and .
Proof: Note that the forward direction is trivial. Suppose for every , then we are done by induction on the number of vertices. Consider an edge and let . Let . Then clearly and , . Thus by our inductive hypothesis we are done.
Now suppose there is a set such that . Consider the graph induced on . Since and so by induction we know that there is a perfect matching in . Let us consider the induced graph on . We claim that for every , . This is because if then , if and only if , . Thus applying the inductive hypothesis we get a perfect matching in . Patching the perfect matchings in and gives us a perfect matching in .
Alternating path: A path in a graph is an alternating path if the edges in the path alternate between and non edges.
Augmenting path: An augmenting path is an alternating path such that its two end points is unmatched.
Suppose we have an augmenting path . Then we can construct a new matching . Note that . This step is called augmenting the augmenting path . Thus if we have the following algorithm:
- Start with an arbitrary matching .
- While there exists an augmenting path :
- Augment path
Lemma: $latex M$ is a maximum matching in if and only if has no augmenting paths.
Proof: Clearly if is a maximum matching then can have no augmenting path since augmenting it would produce a matching such that .
Suppose has no augmenting path and let be a maximum matching. Consider . Notice that the degree of any vertex in is at most . This is because any vertex can have at most edge and at most edge incident on it. Observe that this implies must be a disjoint collection of paths and cycles. Note that every cycle must be of even length since the cycle edges alternate between and . Thus the number of edges in cycles is the same as the number of edges. In even paths the number of edges is the same as the number of edges since they are alternating. Suppose we have an odd length path. There are two possibilities – either it ends with an edge in which case it is augmenting (contradiction since is maximum) or it ends with an edge in which case it is augmenting (contradicting our hypothesis). Thus consists of only even cycles and even paths. Thus .
Finding augmenting paths
Start with all the unmatched vertices and consider a BFS like procedure from them. We grow the forest around them by adding unmatched and matched edges alternatively. Notice that there cannot be an unmatched edge connecting two matched vertices in the same component – since that gives us an odd cycle. Whenever two components are connected – we get an augmenting path.