degree_list_kempe_diameter_fin_eighteen
abbrev
For a fixed graph G on 5 vertices: every tight degree-list assignment into the fixed palette Fin 18 and every two proper L-colourings admit a Kempe chain of length at most 6.
Statement
abbrev degree_list_kempe_diameter_fin_eighteen (G : SimpleGraph (Fin 5)) [DecidableRel G.Adj] : Prop
- Source
- step towards degree_list_kempe_diameter_five
- Verified
- 31 Oct 2026
- Axioms
- none listed
- Built on 1
- degree_list_kempe_stepThe elementary L-valid Kempe change: both colourings respect every list L v, and c₂ is obtained from c₁ by swapping two distinct colours a…
Lean source view module on GitHub
/-- Same Kempe-diameter-6 bound as `degree_list_kempe_diameter_at_most_six` but with the colour type fixed to the finite palette Fin 18. 18 is the palette bound forced by tightness: |⋃_v L v| ≤ Σ_v |L v| = Σ_v deg v = 2|E| ≤ 18. Fixing a finite palette is what turns the statement into a finite, `Decidable`-friendly object. -/ abbrev degree_list_kempe_diameter_fin_eighteen (G : SimpleGraph (Fin 5)) [DecidableRel G.Adj] : Prop := ∀ (L : Fin 5 → Finset (Fin 18)), (∀ v, (L v).card = G.degree v) → ∀ (α β : G.Coloring (Fin 18)), (∀ v, α v ∈ L v) → (∀ v, β v ∈ L v) → ∃ (k : ℕ), k ≤ 6 ∧ ∃ (seq : List (G.Coloring (Fin 18))), seq ≠ [] ∧ seq.head? = some α ∧ seq.getLast? = some β ∧ seq.length - 1 = k ∧ seq.IsChain (degree_list_kempe_step G L)