Statement
Hall’s marriage theorem gives a necessary and sufficient condition for whether a bipartite graph has a perfect matching: for every , if is the neighborhood of in , then must be . Here, the neighborhood of refers to the set of all nodes in that are connected directly to a node in .
An -perfect matching. We can verify Hall’s condition on, for instance, , whose neighborhood is the first four nodes in . , therefore the condition is satisfied.
Proof 1 (Flows)
If there exists with , then a perfect matching is obviously impossible. It remains to prove sufficiency, which can also be done fairly easily by the max-flow min-cut theorem (for more, see flow).
Set up the following flow network:
- Connect the source node with edges of capacity 1 to every node in .
- Direct every edge between and toward with capacity .
- Connect every node in to the sink with edges of capacity .
Clearly, a flow in this network corresponds to a matching on the original bipartite graph. Now, consider any cut in this flow network with finite capacity. Let be the set of nodes in which are still connected to the source. Then, the smallest set we can cut on the right side is exactly the neighborhood of . The size of the resultant cut is then , but since we have for all , this quantity must then be for all possible cuts, and thus the min-cut is exactly with equality achieved when . Therefore, an -flow must exist.
Proof 2 (Constructive)
We induct, and consider 2 cases.
Case 1: For every with and its neighborhood , . In this case, we can just pair any two connected nodes and , as this decreases the RHS of the above inequality by at most 1 for all .
Case 2: There exists with and . By induction, we can perfectly match to . Every remaining subset will still satisfy Hall’s condition because is subtracted from the LHS and at most is subtracted from the RHS.
Takeaways
I think this theorem is quite beautiful as it essentially just compounds necessary conditions until their sum ends up being sufficient. What I mean is this:
When you see the problem, you’ll likely observe that trivially, must be , which is certainly necessary but definitely not sufficient. But then you simply apply this condition to all subsets of , and that turns out to be sufficient! Isn’t that elegant?
Problems
There are candies, each with a potentially different color. Determine whether it’s possible to split them into pairs such that no pair contains two candies of the same color.
Solution
To use Hall’s theorem, we just need to find whether there exists a way to split the candies into nodes on the left and nodes on the right, with edges between candies of both opposite side and color, such that Hall’s condition is satisfied.
First, observe that if contains candies of at least two colors, its neighborhood is all nodes on the right side. Therefore, we only need to consider mono-colored .
Note that if there are candies of color on the left side, there must be at most candies of color on the right side by Hall’s condition. It is therefore both necessary and sufficient that there are candies of each color.
There also exists a more direct inductive argument that is very similar to the one shown above. We again split into two cases.
- If there exists a color that occurs exactly times, simply pair off each of the other candies with a candy of color . For instance, if our colors were , we would just pair .
- Otherwise, we can just remove any pair.
The next few problems are from https://cjquines.com/files/halls.pdf. Also in solutions, will denote the neighborhood of .
Solution
Construct the graph in which each of the 4006 polygons is a vertex, and an edge is drawn between two vertices if their corresponding polygons can be pierced by a single pin. Now we just need to show that for every set of polygons , . Since all polygons have area 1, and are precisely the areas of and respectively, so our desired inequality easily follows since the area defined by must strictly contain .
Solution
Consider the graph in which each row and column its own vertex (so 16 vertices total), and a piece in position corresponds to an edge between nodes and . The constraint means that the degree of every node in this graph is exactly .
Now, for any , the amount of edges incident to cannot exceed the amount incident to . Applying the constraint, we then have , which means for all as desired.