degree_list_kempe_step
abbrev
The elementary L-valid Kempe change: both colourings respect every list L v, and c₂ is obtained from c₁ by swapping two distinct colours a ≠ b on a single nonempty connected component U of the subgraph induced by the a/b-coloured vertices (closed under a/b-coloured neighbours), leaving all other vertices fixed.
Statement
abbrev degree_list_kempe_step (G : SimpleGraph (Fin 5)) {C : Type} [DecidableEq C] (L : Fin 5 → Finset C) (c₁ c₂ : G.Coloring C) : Prop
- Source
- step towards degree_list_kempe_diameter_five
- Verified
- 31 Oct 2026
- Axioms
- none listed
- Used by 2
- degree_list_kempe_diameter_at_most_sixFor a fixed G on 5 vertices, every tight degree-list assignment and every two proper L-colourings admit a Kempe chain of length at most 6…
- degree_list_kempe_diameter_fin_eighteenFor a fixed graph G on 5 vertices: every tight degree-list assignment into the fixed palette Fin 18 and every two proper L-colourings…
Lean source view module on GitHub
/-- The single-step relation of degree-list Kempe reconfiguration, factored out of the target statement. Declared `abbrev` so that, after unfolding, it is definitionally the inline relation used by `degree_list_kempe_diameter_five`, making the assembly proof a plain `exact`. -/ abbrev degree_list_kempe_step (G : SimpleGraph (Fin 5)) {C : Type} [DecidableEq C] (L : Fin 5 → Finset C) (c₁ c₂ : G.Coloring C) : Prop := (∀ v, c₁ v ∈ L v) ∧ (∀ v, c₂ v ∈ L v) ∧ ∃ (a b : C) (U : Set (Fin 5)), a ≠ b ∧ U.Nonempty ∧ (∀ v ∈ U, c₁ v = a ∨ c₁ v = b) ∧ (G.induce U).Connected ∧ (∀ u ∈ U, ∀ v : Fin 5, G.Adj u v → (c₁ v = a ∨ c₁ v = b) → v ∈ U) ∧ (∀ v ∈ U, c₂ v = (if c₁ v = a then b else a)) ∧ (∀ v ∉ U, c₂ v = c₁ v)