AFTD Auto-Formalizing Theoretical Domains

degree_list_kempe_diameter_at_most_six

abbrev

For 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 over an arbitrary finite colour type.

Statement

abbrev degree_list_kempe_diameter_at_most_six (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

/-- For a fixed graph G on Fin 5: every tight degree-list assignment (card L v = deg v) has Kempe diameter at most 6 over an arbitrary finite colour type C. This is exactly the conclusion of `degree_list_kempe_diameter_five`, with G fixed and the list hypothesis quantified over all tight L and all L-colorings. Declared `abbrev` so the target's inline body is definitionally this. -/
abbrev degree_list_kempe_diameter_at_most_six (G : SimpleGraph (Fin 5)) [DecidableRel G.Adj] : Prop := ∀ (C : Type) [Fintype C] [DecidableEq C] (L : Fin 5 → Finset C),
    (∀ v, (L v).card = G.degree v) →
    ∀ (α β : G.Coloring C),
      (∀ v, α v ∈ L v) → (∀ v, β v ∈ L v) →
      ∃ (k : ℕ), k ≤ 6 ∧
        ∃ (seq : List (G.Coloring C)),
          seq ≠ [] ∧ seq.head? = some α ∧ seq.getLast? = some β ∧
          seq.length - 1 = k ∧
          seq.IsChain (degree_list_kempe_step G L)
See it in the graphDiscuss this resultChallenge it