Kőnig's theorem, vertex-cover form: if every matching of a finite bipartite edge set has at most edges, then has a vertex cover of size at most
ProvedOAI.SeymourSecondNeighborhood.Pruning.konigLet be types and a finite set of edges of a bipartite graph. A matching is a subset on which both projections are injective, i.e. no two edges of share a left endpoint or a right endpoint. A vertex cover is a pair of finite sets , such that every edge has or . The statement is K\H{o}nig's theorem in the form needed by the pruning lemma:
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 (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 or is assumed; only is a Finset. Matchings are subsets M ⊆ E with Set.InjOn Prod.fst M and Set.InjOn Prod.snd M.
import Mathlib import Definitions.Def_SeymourSecondNeighborhood import Definitions.Def_SeymourSecondNeighborhood_Image open Finset
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