AFTD Auto-Formalizing Theoretical Domains

simple_graph_reconfiguration_graph

def

For a simple graph G and a natural number k, the k-reconfiguration graph of G is the simple graph whose vertices are the proper k-colorings of G with colors in Fin k, where two colorings are adjacent if and only if they differ on exactly one vertex.

Statement

def simple_graph_reconfiguration_graph {V : Type*} (G : SimpleGraph V) (k : ℕ) :
    SimpleGraph (G.Coloring (Fin k))
Defined in
arXiv:2610.27527 Section 1
Verified
26 Oct 2026
Axioms
none listed
Used by 6

Read back from the Lean

Given a type V, a simple graph G with vertex type V, and a natural number k, simple_graph_reconfiguration_graph G k is the simple graph whose vertices are the proper k-colorings of G (elements of G.Coloring (Fin k)), and where two colorings c₁ and c₂ are adjacent if and only if there exists a unique vertex v : V such that c₁ v ≠ c₂ v (that is, c₁ and c₂ differ at 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

/-- The k-reconfiguration graph of proper k-colorings of a simple graph G, with edges between colorings differing at exactly one vertex. -/
def simple_graph_reconfiguration_graph {V : Type*} (G : SimpleGraph V) (k : ℕ) :
    SimpleGraph (G.Coloring (Fin k)) := {
  Adj := fun c₁ c₂ => ∃! v : V, c₁ v ≠ c₂ v
  symm := ⟨fun _ _ ⟨v, hv, huniq⟩ => ⟨v, ne_comm.mp hv, fun u hu => huniq u (ne_comm.mp hu)⟩⟩
  loopless := ⟨fun _ ⟨_, hv, _⟩ => hv rfl⟩
}
See it in the graphDiscuss this resultChallenge it