simple_graph_reconfiguration_graph
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
- simple_graph_reconfiguration_diam_gt_matchingThe predicate on a natural number Δ asserting that there exists a finite simple graph G on a finite type V with decidable equality and…
- op_1611_min_max_degree_le_eightThe natural number 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
- simple_graph_reconfiguration_diam_le_three_halves_of_bipartiteLet G be a finite bipartite simple graph on a type V with decidable equality and decidable adjacency. For every integer k ≥ G.maxDegree +…
- simple_graph_reconfiguration_not_connected_of_frozen_subgraphIf a simple graph G admits a proper ℓ-coloring α whose restriction to a nonempty subset S is frozen with respect to all ℓ colors, and G…
- simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartiteLet G be a finite bipartite simple graph on a type V with decidable equality and decidable adjacency. For every integer k ≥ G.maxDegree +…
- simple_graph_reconfiguration_frozen_core_reachable_eqLet G be a simple graph, s a subset of vertices, and α a proper k-coloring of G whose restriction to the induced subgraph on s is frozen…
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⟩ }