halls_theorem (706B)
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 - notion of hall blocker: if a [bipartite_graph] has not [perfect_matching] then... cf https://blog.computationalcomplexity.org/2026/07/bipartite-perfect-matching-in.html?m=1 5 6 [Hall's_theorem_proof] 7 8 Consequence: [regular_bipartite_graph_perfect_matching] 9 10 Consequence for [satisfiability_boolean]: [3sat_3_occurrences_exactly3], but contrast [3sat_3_occurrences_atmost3] 11 12 Extension to [hypergraphs]: 13 - https://en.wikipedia.org/wiki/Hall-type_theorems_for_hypergraphs#Haxell's_condition:_smallest_transversal 14 - cf [transversal] 15 16 Up: [graph]