Theorem 8.2.1 — Hall's theorem
ProvedMatousekLP.Integrality.hallbipartite-graphgraph-theorymatchingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a finite bipartite graph with bipartition . For a set let
be its neighbourhood. If holds for every , then has a matching that covers all vertices in , that is, a matching such that every is an end-vertex of some edge of .
Hall's condition is also necessary, but the book states and proves only this direction, as a consequence of König's theorem.
Formalization Note The bipartition is given explicitly as finite sets (IsBipartition G X Y); the matching is a finite set of edges of .
Preamble
import Mathlib import Definitions.Def_MatousekLP_Integrality_BipartiteGraph
Formal statement
namespace MatousekLP.Integrality
theorem hall {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(X Y : Finset V) (hXY : IsBipartition G X Y)
(hN : ∀ T ⊆ X, T.card ≤ (neighborhood G Y T).card) :
∃ M : Finset (Sym2 V), IsMatching G M ∧ ∀ x ∈ X, ∃ e ∈ M, x ∈ e := by sorry
end MatousekLP.Integrality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 144, Theorem 8.2.1 (Hall's theorem)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.