Theorem 14.3 — König's Theorem
ProvedVanderbeiLP.Networks.konig_theoremSuppose there are girls and boys, that every girl knows exactly boys, and that every boy knows exactly girls, where "knowing" is symmetric: girl and boy either know each other or do not. Write when they do. If , then marriages can be arranged with everybody knowing his or her spouse: there is a bijection from girls to boys with
In graph language: every -regular bipartite graph with has a perfect matching. Vanderbei derives it as a combinatorial application of the Integrality Theorem 14.2.
Formalization Note Girls and boys are both indexed by Fin n, and the symmetric relation is a single relation knows i j between girl and boy . The hypothesis is implicit in the book: its proof puts flow on each arc, and for the conclusion is false. The network in the proof need not be connected; the statement carries no connectedness hypothesis.
import Mathlib
namespace VanderbeiLP.Networks
/-- **Theorem 14.3, König's Theorem** (Vanderbei, *Linear Programming*, 4th ed., p. 216).
Suppose there are `n` girls and `n` boys, every girl knows exactly `k` boys and every boy knows
exactly `k` girls, "knowing" being symmetric (`knows i j`: girl `i` and boy `j` know each other).
Then `n` marriages can be arranged with everybody knowing his or her spouse: there is a
bijection `σ` from girls to boys with girl `i` knowing boy `σ i`. The hypothesis `0 < k` is
implicit in the book (its proof puts flow `1/k` on each arc; with `k = 0 < n` the claim fails). -/
theorem konig_theorem (n k : ℕ) (hk : 0 < k) (knows : Fin n → Fin n → Prop)
[DecidableRel knows]
(hgirl : ∀ i : Fin n, (Finset.univ.filter (fun j => knows i j)).card = k)
(hboy : ∀ j : Fin n, (Finset.univ.filter (fun i => knows i j)).card = k) :
∃ σ : Fin n ≃ Fin n, ∀ i : Fin n, knows i (σ i) := by sorry
end VanderbeiLP.Networks
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.