Matchings and Hall's Theorem
For a finite bipartite graph, decide whether every left vertex can be matched to a different right neighbour, and prove Hall's condition is necessary and sufficient.
What a learner can do afterwards
- State Hall's condition and check it on a small bipartite graph
- Prove that Hall's condition is sufficient, not merely necessary
- Recast an assignment problem as a matching and read off what blocks a full pairing
1 · Read
In a finite bipartite graph, the vertex sets L and R have edges only between the sides. A matching is a set of edges with no shared endpoint. A left-covering matching gives every vertex in L a different neighbour in R. It may leave right vertices unused. A perfect matching covers both sides. Equal side sizes are necessary for a perfect matching, but do not guarantee one.
For S contained in L, N(S) contains every right vertex adjacent to at least one member of S. Merge the neighbour lists and count each job once. Hall's condition is |N(S)| >= |S| for every S contained in L. Bars around a set name mean its number of members. The empty set passes because 0 >= 0. Hall's theorem says this condition is necessary and sufficient for a left-covering matching.
H and I have three distinct neighbours together.
Hall's condition is necessary: a matching covering the left side assigns |S| different neighbours to every group S. If |N(S)| < |S|, that group blocks such a matching. For example, two applicants who both suit only one job each have a neighbour, but their pair has too few. Checking only individual applicants misses this obstruction. More applicants than available jobs also blocks a full assignment.
Each left vertex is either included or omitted, giving 2^n subsets for n left vertices. A full Hall check may omit the empty subset because it always passes. That leaves 2^n - 1 nonempty groups. Check singleton groups as well as larger ones.
To enlarge a matching, start from an unmatched left vertex. Search along unused edges left to right and matched edges right to left. An augmenting path ends at an unmatched right vertex and repeats no vertices. Flip it by removing its matched edges and adding its unused edges. This gains one pair. A matching with no edge you can add may still grow by rerouting. Choosing any suitable pair and deleting its endpoints need not preserve Hall's condition.
If an exhaustive search from one unmatched left vertex reaches no unmatched right vertex, let S and T be the reached left and right sets. Every neighbour of S is reached: unused edges are explored, while each reached matched left vertex's partner was already reached. Thus N(S)=T. Each vertex in T is matched, and its partner is reached. Those partners are exactly S except the unmatched start. Therefore |S|=|T|+1, so S violates Hall.
To prove sufficiency, assume Hall's condition and choose a largest matching, which exists because the graph is finite. If a left vertex is unmatched, search from it. An augmenting path would increase the matching, contradicting its size. Without such a path, the search gives N(S)=T and |S|=|T|+1, contradicting Hall's condition. Both alternatives are impossible, so the largest matching covers the left side.
A tight set S has exactly |S| neighbours. In a left-covering matching, S uses all those neighbours, so vertices outside S need partners outside N(S). If a group has s members and only t neighbours, with s>t, at least s-t members stay unmatched. Any matching then has at most |L|-(s-t) pairs. Prove a claimed maximum by giving an upper bound and a matching attaining it.
Check every group for enough jobs, then pair off or name the blocking group.
This lesson, its questions, flashcards and worked solutions were written for this dataset.
These readings, matching questions, flashcards and explanations were written for this dataset.
More to read
Which vertices must be covered?
An assignment problem can be represented by a bipartite graph. Put applicants on the left and jobs on the right. Join an applicant to a job exactly when that assignment is allowed.
A matching selects allowed edges without using any vertex twice. Both restrictions matter. An applicant cannot receive two jobs, and a job cannot receive two applicants.
Covering the left side means giving every applicant a different suitable job. Some jobs may remain unused. A perfect matching has the additional requirement that every right vertex is covered too. Its two sides must therefore have equal sizes, although equal sizes alone do not guarantee suitable pairs.
For a group S of applicants, N(S) is the set of jobs suitable for at least one member. A job shared by several applicants appears only once in this set. Any matching covering S needs |S| different jobs inside N(S), so |N(S)| must be at least |S|. Hall's theorem says that, in a finite bipartite graph, checking this inequality for every left-side group is also sufficient.
Proving Hall's theorem with flow
Let a finite bipartite graph have n left vertices, with n>0. Build a directed network. Give each source-to-left edge capacity 1, each allowed left-to-right edge capacity n+1, and each right-to-sink edge capacity 1.
Starting from zero flow, augmenting by integer bottleneck amounts keeps every flow integral. Each augmentation increases the flow value by at least one, and the source can supply at most n units. The process therefore reaches an integral maximum flow. Its used middle edges form a matching because the outer edges permit at most one unit through each left or right vertex.
The cut separating the source from all other vertices has capacity n. A minimum cut cannot cross a middle edge, since one such edge has capacity n+1. Let S be the left vertices on its source side. Every vertex of N(S) must also be on that side. The cut capacity is at least n-|S|+|N(S)|: it includes the source edges for left vertices outside S and the sink edges for the right vertices on the source side.
If Hall holds, every minimum cut has capacity at least n. Max-flow min-cut then gives an integral flow of value n and a matching covering the left side. Conversely, if |N(S)|<|S|, put the source, S and N(S) on the source side of a cut. This cut has capacity n-|S|+|N(S)|<n, preventing a left-covering matching. If n=0, the empty matching already covers the left side.
Rerouting a matching
A maximal matching has no edge that can be added while keeping its present edges. A maximum matching has the largest possible number of edges. A matching can be maximal without being maximum.
Consider the allowed edges F-U, D-U, D-V, E-V and E-W. Start with the matching D-U and E-V. No remaining edge can be added directly: each touches an applicant or job already in use. Yet the matching can grow.
Read the path F-U-D-V-E-W in order. Its edges alternate between unused and matched. Both endpoints are unmatched. Remove D-U and E-V, then add F-U, D-V and E-W. The result has three pairs instead of two, with no repeated endpoint.
When searching from an unmatched applicant, explore every allowed continuation before concluding that no augmenting path exists. If no free job is reached, let S be the reached applicants and T the reached jobs. All neighbours of S are in T, and each job in T is matched to a reached applicant. These partners account for every member of S except the unmatched start. Thus |N(S)|=|S|-1. The reached group is a certificate that a left-covering matching is impossible.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Optional connections
This opens up
Nothing builds on it yet.
17 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.