Theorem 1.1 — arbitrarily large graphs with small connected matchings
ProvedOAI.HadwigerCounterexample.exists_graphsThis is the main result of the source preprint (Theorem 1.1, p. 3). There are arbitrarily large integers for which an -vertex finite simple graph satisfies
where is the independence number and is the connected-matching number (the largest size of a matching whose edges are pairwise touching). Precisely, for every bound there is an and a graph on vertices with these properties.
Combined with the matching–minor bound (Proposition 3.5), this forces the Hadwiger number below while the chromatic number is at least , disproving Hadwiger's conjecture. The graphs are produced by a probabilistic frame construction over ; the constant is the paper's fixed linear coefficient.
Formalization Note. Transcribed from the authors' Lean theorem OAI.HadwigerCounterexample.exists_graphs (Main.lean). Graphs are SimpleGraph (Fin m); is indepNum (an ℕ∞); is the natural-valued connectedMatchingNumber, cast to ℚ for the strict inequality. The lower bound ensures nonemptiness and matches the authors' statement.
import Mathlib import Definitions.Def_HadwigerMatching_Defs import Definitions.Def_ListHadwiger open OAI.HadwigerMatching OAI.LinearListHadwiger
namespace OAI.HadwigerCounterexample
theorem exists_graphs (M : ℕ) : ∃ m : ℕ, max M 5 ≤ m ∧
∃ G : SimpleGraph (Fin m), G.indepNum ≤ 2 ∧
(connectedMatchingNumber G : ℚ) < (m : ℚ) / 100 := by sorry
end OAI.HadwigerCounterexampleConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.