Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Matching bound for the augmented bipartite graph of two families of pairs: every matching of Γ\GammaΓ has at most ∣Z∣+∣H∣|Z|+|H|∣Z∣+∣H∣ edges

Open
OAI.SeymourSecondNeighborhood.Pruning.matching_bound

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

combinatoricsgraph-theoryseymour-second-neighborhood

Let XXX be a finite set with an arbitrary binary relation →\to→, and let R,C⊆X×XR,C\subseteq X\times XR,C⊆X×X be two families of ordered pairs. A left member (p,j)∈R(p,j)\in R(p,j)∈R and a right member (i,s)∈C(i,s)\in C(i,s)∈C conflict if p→ip\to ip→i and s→js\to js→j; a conflict contributes the point (i,j)(i,j)(i,j) to ZZZ and the point (p,s)(p,s)(p,s) to HHH. A member (p,j)∈R(p,j)\in R(p,j)∈R covers a point (i,j)(i,j)(i,j) when p→ip\to ip→i, and a member (i,s)∈C(i,s)\in C(i,s)∈C covers (i,j)(i,j)(i,j) when s→js\to js→j. The augmented bipartite graph Γ\GammaΓ has left vertex set R⊔ZLR\sqcup Z_LR⊔ZL​ and right vertex set C⊔ZRC\sqcup Z_RC⊔ZR​, where ZL,ZRZ_L,Z_RZL​,ZR​ are two copies of ZZZ; its edges join each conflicting pair (r,c)∈R×C(r,c)\in R\times C(r,c)∈R×C, each r∈Rr\in Rr∈R to the right copy of every point of ZZZ it covers, and each c∈Cc\in Cc∈C to the left copy of every point of ZZZ it covers (there are no edges between ZLZ_LZL​ and ZRZ_RZR​). The statement is that

∣M∣  ≤  ∣Z∣+∣H∣for every matching M of Γ,|M|\;\le\;|Z|+|H|\qquad\text{for every matching }M\text{ of }\Gamma,∣M∣≤∣Z∣+∣H∣for every matching M of Γ,

where a matching is a set of edges with pairwise distinct left endpoints and pairwise distinct right endpoints. This is the core of Section 3 of the manuscript, where it is proved by a rank argument: with generic real coefficients axy,bxya_{xy},b_{xy}axy​,bxy​ attached to the arrows, four matrices L,N,A,BL,N,A,BL,N,A,B satisfy NL=ABNL=ABNL=AB, a maximum matching with the fewest member–member edges is encoded by rank⁡L\operatorname{rank}LrankL, rank⁡N\operatorname{rank}NrankN and dim⁡ker⁡A\dim\ker AdimkerA, and Lemma 3.2 (Pruning.lemma_3_2, kernels at maximum support rank) controls the kernel vectors. Together with K\H{o}nig's theorem (Pruning.konig) it implies the pruning lemma Pruning.lemma_3_1, and hence (through prop_4_1, lemma_2_2 and lemma_2_3) Seymour's second-neighborhood conjecture. The bound is tight: for the complete loopless relation on nnn points with R=C=X×XR=C=X\times XR=C=X×X one has ∣M∣=2n2=∣Z∣+∣H∣|M|=2n^2=|Z|+|H|∣M∣=2n2=∣Z∣+∣H∣.

Formalization note. Both sides of Γ\GammaΓ are encoded as (X × X) ⊕ (X × X): Sum.inl for members of RRR (left) or CCC (right), Sum.inr for the copies of points of ZZZ. The hypothesis hM says every element of M is an edge of Γ\GammaΓ of one of the three kinds, and h₁, h₂ say M is a matching.

Preamble
import Mathlib
import Definitions.Def_SeymourSecondNeighborhood
import Definitions.Def_SeymourSecondNeighborhood_Image

open Finset
Formal statement
namespace OAI.SeymourSecondNeighborhood.Pruning

variable {X : Type*} [Fintype X] [DecidableEq X]

/-- **Matching bound in the augmented bipartite graph `Γ`.** The graph `Γ` has left vertex set
`R ⊔ Z` (members of `R`, and left copies `Sum.inr z` of the points `z ∈ Z = pointsZ arrow R C`)
and right vertex set `C ⊔ Z` (members of `C`, and right copies of the points of `Z`), encoded as
`(X × X) ⊕ (X × X)` on both sides. Its edges are
* the conflict edges `(inl l, inl c)` with `l ∈ R`, `c ∈ C`, `Conflict arrow l c`;
* the left-cover edges `(inl l, inr z)` with `l ∈ R`, `z ∈ Z`, `CoversL arrow l z`;
* the right-cover edges `(inr z, inl c)` with `z ∈ Z`, `c ∈ C`, `CoversR arrow c z`.

Every matching `M` of `Γ` (a set of edges of `Γ` on which both projections are injective) has at
most `|Z| + |H|` edges, where `H = pointsH arrow R C`. -/
theorem matching_bound (arrow : X → X → Prop) (R C : Finset (X × X))
    (M : Finset (((X × X) ⊕ (X × X)) × ((X × X) ⊕ (X × X))))
    (hM : ∀ e ∈ M,
      (∃ l ∈ R, ∃ c ∈ C, e = (Sum.inl l, Sum.inl c) ∧ Conflict arrow l c) ∨
      (∃ l ∈ R, ∃ z ∈ pointsZ arrow R C, e = (Sum.inl l, Sum.inr z) ∧ CoversL arrow l z) ∨
      (∃ z ∈ pointsZ arrow R C, ∃ c ∈ C, e = (Sum.inr z, Sum.inl c) ∧ CoversR arrow c z))
    (h₁ : Set.InjOn Prod.fst (M : Set (((X × X) ⊕ (X × X)) × ((X × X) ⊕ (X × X)))))
    (h₂ : Set.InjOn Prod.snd (M : Set (((X × X) ⊕ (X × X)) × ((X × X) ⊕ (X × X))))) :
    M.card ≤ (pointsZ arrow R C).card + (pointsH arrow R C).card := 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