Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Kőnig's theorem, vertex-cover form: if every matching of a finite bipartite edge set E⊆A×BE\subseteq A\times BE⊆A×B has at most kkk edges, then EEE has a vertex cover of size at most kkk

Proved
OAI.SeymourSecondNeighborhood.Pruning.konig

by SamenHossain · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryseymour-second-neighborhood

Let A,BA,BA,B be types and E⊆A×BE\subseteq A\times BE⊆A×B a finite set of edges of a bipartite graph. A matching is a subset M⊆EM\subseteq EM⊆E on which both projections are injective, i.e. no two edges of MMM share a left endpoint or a right endpoint. A vertex cover is a pair of finite sets KA⊆AK_A\subseteq AKA​⊆A, KB⊆BK_B\subseteq BKB​⊆B such that every edge (a,b)∈E(a,b)\in E(a,b)∈E has a∈KAa\in K_Aa∈KA​ or b∈KBb\in K_Bb∈KB​. The statement is K\H{o}nig's theorem in the form needed by the pruning lemma:

if every matching M⊆E satisfies ∣M∣≤k, then there is a vertex cover with ∣KA∣+∣KB∣≤k.\text{if every matching }M\subseteq E\text{ satisfies }|M|\le k,\ \text{then there is a vertex cover with }|K_A|+|K_B|\le k .if every matching M⊆E satisfies ∣M∣≤k, then there is a vertex cover with ∣KA​∣+∣KB​∣≤k.

Equivalently, the minimum size of a vertex cover of a finite bipartite graph equals the maximum size of a matching (the other inequality is trivial). It is used in the proof of the pruning lemma OAI.SeymourSecondNeighborhood.Pruning.lemma_3_1: the manuscript bounds a maximum matching of an augmented bipartite graph by ∣Z∣+∣H∣|Z|+|H|∣Z∣+∣H∣ (matching_bound) and then takes a vertex cover of that size, whose original members are deleted. The theorem can be derived from Hall's marriage theorem (available in Mathlib as Finset.all_card_le_biUnion_card_iff_exists_injective) in its deficiency form.

Formalization note. No finiteness of AAA or BBB is assumed; only EEE is a Finset. Matchings are subsets M ⊆ E with Set.InjOn Prod.fst M and Set.InjOn Prod.snd M.

Preamble
import Mathlib
import Definitions.Def_SeymourSecondNeighborhood
import Definitions.Def_SeymourSecondNeighborhood_Image

open Finset
Formal statement
namespace OAI.SeymourSecondNeighborhood.Pruning

/-- **Kőnig's theorem** (vertex-cover form) for a finite bipartite graph given by its edge set
`E ⊆ A × B`. A *matching* is a set of edges `M ⊆ E` on which both projections are injective
(no two edges share a left endpoint or a right endpoint). If every matching in `E` has at most
`k` edges, then there is a *vertex cover* `KA ⊆ A`, `KB ⊆ B` (every edge of `E` has its left
endpoint in `KA` or its right endpoint in `KB`) with `|KA| + |KB| ≤ k`. -/
theorem konig {A B : Type*} (E : Finset (A × B)) (k : ℕ)
    (hk : ∀ M ⊆ E, Set.InjOn Prod.fst (M : Set (A × B)) →
      Set.InjOn Prod.snd (M : Set (A × B)) → M.card ≤ k) :
    ∃ KA : Finset A, ∃ KB : Finset B,
      (∀ e ∈ E, e.1 ∈ KA ∨ e.2 ∈ KB) ∧ KA.card + KB.card ≤ k := by
  sorry

end OAI.SeymourSecondNeighborhood.Pruning
Source
Statement extracted from Section 3 of OpenAI, *A proof of Seymour's second-neighborhood conjecture*, preprint, September 23, 2026, https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-proof-of-Seymours-second-neighborhood-conjecture-September-23-2026/paper.pdf; Kőnig's theorem: D. Kőnig, Matematikai és Fizikai Lapok 38 (1931) 116–119.

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