Proposition 3.5 — the matching–minor bound
ProvedOAI.HadwigerMatching.full_matching_minor_propositionProposition 3.5 of the source preprint (p. 15). For every finite nonempty graph of order , with Hadwiger number and connected-matching number ,
In particular, if , and , then
The bound counts small branch sets in a complete-minor model: the singleton branches form a clique and can be paired, and together with the two-vertex branches they form one touching matching, which controls the deficit. This is the counting inequality that converts the connected-matching bound of Theorem 1.1 into a clique-minor estimate, following the connected-matching approach of Cambie.
Formalization Note. Transcribed verbatim from the authors' Lean theorem OAI.HadwigerMatching.full_matching_minor_proposition (HadwigerMatching/Main.lean). The order , Hadwiger number and connected-matching number are introduced as let-bindings; inequalities are over ℚ; is represented by chromaticNumber.toNat (finite on a finite graph).
import Mathlib import Definitions.Def_HadwigerMatching_Defs import Definitions.Def_ListHadwiger open OAI.HadwigerMatching OAI.LinearListHadwiger
namespace OAI.HadwigerMatching
theorem full_matching_minor_proposition
(V : Type) [Fintype V] [Nonempty V] (G : SimpleGraph V) :
let m : ℕ := Fintype.card V
let h : ℕ := LinearListHadwiger.hadwigerNumber G
let c : ℕ := HadwigerMatching.connectedMatchingNumber G
(h : ℚ) ≤ ((m : ℚ) + 4 * (c : ℚ) + 2) / 3 ∧
(G.indepNum ≤ 2 →
(c : ℚ) < (m : ℚ) / 100 →
5 ≤ m →
(h : ℚ) < 26 * (m : ℚ) / 75 + 2 / 3 ∧
26 * (m : ℚ) / 75 + 2 / 3 < (m : ℚ) / 2 ∧
(m : ℚ) / 2 ≤ (G.chromaticNumber.toNat : ℚ)) := by sorry
end OAI.HadwigerMatchingConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.