Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Touching matchings and the connected-matching number

Definition
HadwigerMatching_Defs

by LG · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryhadwigermatching

A connected matching in a simple graph GGG is a matching whose edges are pairwise touching: two disjoint edges touch when some edge of GGG joins an endpoint of one to an endpoint of the other. Formally, a finite family MMM of vertex sets is a touching matching when every member is a two-vertex clique (an edge), distinct members are disjoint, and every two distinct members are joined by an edge of GGG.

The connected-matching number cm(G)\mathrm{cm}(G)cm(G) is the largest cardinality of a touching matching,

cm(G)=sup⁡{ ∣M∣:M is a touching matching of G }.\mathrm{cm}(G)=\sup\{\,|M| : M\text{ is a touching matching of }G\,\}.cm(G)=sup{∣M∣:M is a touching matching of G}.

For a finite vertex type this supremum is attained. This is the quantity bounded above by m/100m/100m/100 in the counterexample construction (Theorem 1.1 of the source preprint, p. 3).

Formalization Note. Transcribed verbatim from the authors' Lean development (OAI.Combinatorics.HadwigerMatching.Definitions). The number is a natural-valued sSup; on finite graphs the set of achievable cardinalities is nonempty (the empty matching) and bounded by the order, so the supremum is a maximum.

Definition code
import Mathlib.Combinatorics.SimpleGraph.Clique

namespace OAI

namespace HadwigerMatching

universe u
variable {V : Type u}

/-- A finite matching whose edges are pairwise touching: each member is a
two-vertex clique, and distinct members are disjoint and joined by an edge. -/
def IsTouchingMatching (G : SimpleGraph V) (M : Finset (Finset V)) : Prop :=
  (∀ e ∈ M, e.card = 2 ∧ G.IsClique (e : Set V)) ∧
  (∀ e ∈ M, ∀ f ∈ M, e ≠ f → Disjoint e f) ∧
  (∀ e ∈ M, ∀ f ∈ M, e ≠ f →
    ∃ v ∈ e, ∃ w ∈ f, G.Adj v w)

/-- The supremum of the cardinalities of pairwise touching matchings.
For finite vertex types, this supremum is attained. -/
noncomputable def connectedMatchingNumber (G : SimpleGraph V) : ℕ :=
  sSup {n : ℕ | ∃ M : Finset (Finset V), IsTouchingMatching G M ∧ M.card = n}

end HadwigerMatching

end OAI
Source
https://github.com/openai/math/blob/main/preprints/A-counterexample-to-Hadwigers-conjecture-September-23-2026/paper.pdf , p. 3 (definition of connected matching and cm(G)); authors' Lean: https://github.com/openai/math/blob/main/lean/OAI/Combinatorics/HadwigerMatching/Definitions.lean
Human review
  • Endorsed by Shuze Chen · Nov 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Nov 21, 2026

    Confirmed by the mission captain (proposal self-audit).

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