halls_theorem (531B)
1 # Hall's theorem 2 3 In a [bipartite_graph] (X, Y), there is a [matching] incident to each [vertex] of X iff for each [subset] W of X, we have |W| \leq |Neighbors(W)|. 4 5 [Hall's_theorem_proof] 6 7 Consequence: [regular_bipartite_graph_perfect_matching] 8 9 Consequence for [satisfiability_boolean]: [3sat_3_occurrences_exactly3], but contrast [3sat_3_occurrences_atmost3] 10 11 Extension to [hypergraphs]: 12 - https://en.wikipedia.org/wiki/Hall-type_theorems_for_hypergraphs#Haxell's_condition:_smallest_transversal 13 - cf [transversal] 14 15 Up: [graph]