AFTD Auto-Formalizing Theoretical Domains

simple_graph_reconfiguration_diam_gt_matching

def

The predicate on a natural number Δ asserting that there exists a finite simple graph G on a finite type V with decidable equality and decidable adjacency such that G has maximum degree equal to Δ and the sum of the cardinality of V (coerced to ℕ∞) and the matching number graph_matching_num G is strictly less than the diameter of the (Δ+2)-colouring reconfiguration graph (simple_graph_reconfiguration_graph G (Δ + 2)).diam.

Statement

def simple_graph_reconfiguration_diam_gt_matching (Δ : ℕ) : Prop
Defined in
arXiv:2611.17022 Sec. 8, Question 3
Verified
14 Nov 2026
Axioms
none listed
Built on 2
  • simple_graph_reconfiguration_graphFor a simple graph G and a natural number k, the k-reconfiguration graph of G is the simple graph whose vertices are the proper…
  • graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
Used by 3

Read back from the Lean

For a given natural number Δ, simple_graph_reconfiguration_diam_gt_matching Δ asserts that there exist: 1. A type V with Fintype V and DecidableEq V instances, and 2. A simple graph G on V with a DecidableRel G.Adj instance, such that: - The maximum degree of G is Δ (G.maxDegree = Δ), and - The sum (in ℕ∞) of the number of vertices of V (Fintype.card V) and the matching number of G (graph_matching_num G, defined as the supremum of M.edgeSet.encard over all matching subgraphs M of G) is strictly less than the diameter (diam) of the reconfiguration graph of proper (Δ + 2)-colorings of G (where two colorings c₁, c₂ : G.Coloring (Fin (Δ + 2)) are adjacent if and only if they differ on exactly one vertex).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate on Δ : ℕ asserting existence of a finite graph with maxDegree Δ whose (Δ+2)-recoloring diameter exceeds |V| + μ. -/
def simple_graph_reconfiguration_diam_gt_matching (Δ : ℕ) : Prop := ∃ (V : Type) (_ : Fintype V) (_ : DecidableEq V) (G : SimpleGraph V) (_ : DecidableRel G.Adj),
    G.maxDegree = Δ ∧
    (Fintype.card V : ℕ∞) + graph_matching_num G < (simple_graph_reconfiguration_graph G (Δ + 2)).diam
See it in the graphDiscuss this resultChallenge it