Checking Hall's Condition

Checking Hall's condition naively requires examining all $2^{|L|}$ subsets, which is too slow for any reasonable input size.

Instead, run Kuhn's algorithm first. If the matching size equals $|L|$, Hall's condition holds (by the theorem). If the matching is smaller, you can find the violating subset by looking at unmatched vertices in $L$ and which vertices they can reach via alternating paths. This subset fails Hall's condition.