Introduction
We first note that itβs necessary for the most frequent candy to appear at most times, i.e. . To show that this condition is also sufficient, we induct on and split into two cases:
- Tight (): We can pair the same-color candies with all the others.
- Loose (): We can pair any two different-color candies, and the condition will still hold.
The general flow of tight-slack induction is:
- Derive several necessary inequalities.
- Prove sufficiency by induction. When an inequality is tight, we must find a forced move and prove its validity; otherwise, we must show that any move is valid.
Hallβs marriage theorem
To first derive some necessary conditions, it may help to consider some examples. Draw some graphs that have perfect matchings and some that donβt, and think about what makes/breaks them.
The necessary condition
Consider some subset of nodes on the left side , and denote its neighborhood as the set of right-side nodes that connect to at least one node in . Then, itβs necessary that for all , .
We can now prove sufficiency (by the way, denotes the number of nodes on each side, so there are there nodes in total):
The tight case
If there exists a subset of left-side nodes such that and , we can perfectly match to by induction, then delete both and from the graph. Note that the Hall condition still holds for all remaining subsets. In particular, consider a remaining subset . We knew that prior to deletion, . Since , we can subtract from both sides to see that afterward, still, as desired.
The slack case
When all subsets of left-side nodes with satisfy , we can pair any two nodes together and delete both from the graph. This decreases the RHS of each inequality by at most 1, so they all still hold.