Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 14.3 — König's Theorem

Proved
VanderbeiLP.Networks.konig_theorem

by mikedeng1 · Oct 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsmatchingnetwork-flowsp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Suppose there are nnn girls and nnn boys, that every girl knows exactly kkk boys, and that every boy knows exactly kkk girls, where "knowing" is symmetric: girl iii and boy jjj either know each other or do not. Write i∼ji\sim ji∼j when they do. If k≥1k\ge 1k≥1, then nnn marriages can be arranged with everybody knowing his or her spouse: there is a bijection σ\sigmaσ from girls to boys with

i∼σ(i)for every girl i.i\sim\sigma(i)\qquad\text{for every girl }i.i∼σ(i)for every girl i.

In graph language: every kkk-regular bipartite graph with k≥1k\ge1k≥1 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 iii and boy jjj. The hypothesis k≥1k\ge1k≥1 is implicit in the book: its proof puts flow 1/k1/k1/k on each arc, and for k=0<nk=0<nk=0<n the conclusion is false. The network in the proof need not be connected; the statement carries no connectedness hypothesis.

Preamble
import Mathlib
Formal statement
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
Source
Vanderbei, Linear Programming: Foundations and Extensions, 4th ed., Springer 2014, p. 216 (PDF 227), Theorem 14.3 and the clarifying paragraph after it
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me