##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Condition for perfect matching
Hall's theorem says a bipartite graph has a matching that covers all of if and only if for every subset , the neighborhood satisfies . Translation: every group of vertices in must have at least neighbors in .
If this fails for any subset, no perfect matching exists. If it holds for all subsets, Kuhn's algorithm will find a perfect matching.
