AFTD Auto-Formalizing Theoretical Domains

degree_list_kempe_chain_symm

theoremverified

Reversal of degree-list Kempe chains: if α can reach β in k steps, then β can reach α in k steps.

Statement

theorem degree_list_kempe_chain_symm {n : ℕ} (G : SimpleGraph (Fin n))
    {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C)
    (α β : G.Coloring C) (k : ℕ)
    (seq : List (G.Coloring C))
    (hne : seq ≠ []) (hhead : seq.head? = some α) (hlast : seq.getLast? = some β)
    (hlen : seq.length - 1 = k)
    (hchain : seq.IsChain (fun c₁ c₂ => (∀ v, c₁ v ∈ L v) ∧ (∀ v, c₂ v ∈ L v) ∧
      ∃ (a b : C) (U : Set (Fin n)),
        a ≠ b ∧ U.Nonempty ∧ (∀ v ∈ U, c₁ v = a ∨ c₁ v = b) ∧
        (G.induce U).Connected ∧
        (∀ u ∈ U, ∀ v : Fin n, 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))) :
    ∃ (seq' : List (G.Coloring C)),
      seq' ≠ [] ∧ seq'.head? = some β ∧ seq'.getLast? = some α ∧
      seq'.length - 1 = k ∧
      seq'.IsChain (fun c₁ c₂ => (∀ v, c₁ v ∈ L v) ∧ (∀ v, c₂ v ∈ L v) ∧
        ∃ (a b : C) (U : Set (Fin n)),
          a ≠ b ∧ U.Nonempty ∧ (∀ v ∈ U, c₁ v = a ∨ c₁ v = b) ∧
          (G.induce U).Connected ∧
          (∀ u ∈ U, ∀ v : Fin n, 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))
Source
step towards three_connected_degree_list_kempe_quadratic_diameter
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • degree_list_kempe_step_symmetricThe degree-list Kempe step transition relation is symmetric: if c₂ is obtained from c₁ by an L-valid Kempe change swapping colors a and b…

The proof, explained

The theorem reverses a sequence of degree-list Kempe steps from α to β to produce a sequence from β to α of the same length k. The witness chosen is `seq.reverse`. Its endpoints and length are checked using elementary properties of list reversal, and the chain condition follows because individual Kempe steps are symmetric (`degree_list_kempe_step_symmetric`).

  1. We choose the reversed sequence `seq.reverse` as the candidate chain seq'.

    To reach α from β in k steps, we take the reversal of the original sequence seq. This leaves five subgoals: showing that `seq.reverse` is non-empty, starts at β, ends at α, has length k + 1, and satisfies the Kempe chain condition at each step.

    line 25

      refine ⟨seq.reverse, ?_, ?_, ?_, ?_, ?_⟩
  2. The reversed sequence is non-empty.

    Because the original sequence `seq` is non-empty (hypothesis `hne`), its reversal `seq.reverse` is also non-empty.

    line 26

    uses List.reverse_ne_nil_iff.mpr

      · exact List.reverse_ne_nil_iff.mpr hne
  3. The first coloring of `seq.reverse` is β.

    By `List.head?_reverse`, the head of `seq.reverse` is the last element of `seq`, which is β by hypothesis `hlast`.

    line 27

    uses List.head?_reverse

      · rw [List.head?_reverse, hlast]
  4. The last coloring of `seq.reverse` is α.

    By `List.getLast?_reverse`, the last element of `seq.reverse` is the head of `seq`, which is α by hypothesis `hhead`.

    line 28

    uses List.getLast?_reverse

      · rw [List.getLast?_reverse, hhead]
  5. The number of steps in `seq.reverse` is k.

    Reversing a list preserves its length (`List.length_reverse`), so `seq.reverse.length - 1` equals `seq.length - 1`, which is k by hypothesis `hlen`.

    line 29

    uses List.length_reverse

      · rw [List.length_reverse, hlen]
  6. Every consecutive transition in `seq.reverse` is a valid degree-list Kempe step.

    By `List.isChain_reverse`, a reversed sequence is a chain for relation R if and only if the original sequence is a chain for the converse relation (c₁, c₂) ↦ R(c₂, c₁). It thus suffices to show that each forward step from c₁ to c₂ can be reversed. Deconstructing the step parameters (colors a, b and component U) from hypothesis h, `degree_list_kempe_step_symmetric` establishes that c₁ is obtained from c₂ by a valid degree-list Kempe step.

    lines 30–34

    uses List.isChain_reverse, degree_list_kempe_step_symmetric

      · rw [List.isChain_reverse]
        refine hchain.imp ?_
        intro c₁ c₂ h
        rcases h with ⟨hL₁, hL₂, a, b, U, hab, hU_ne, hU_colors, hU_conn, hU_closed, hc₂_in, hc₂_out⟩
        exact degree_list_kempe_step_symmetric G L c₁ c₂ hL₁ hL₂ a b U hab hU_ne hU_colors hU_conn hU_closed hc₂_in hc₂_out
List.reverse_ne_nil_iff.mpr
If a list is non-empty, then its reversal is non-empty.
List.head?_reverse
The first element of a reversed list is the last element of the original list.
List.getLast?_reverse
The last element of a reversed list is the first element of the original list.
List.length_reverse
The length of a reversed list equals the length of the original list.
List.isChain_reverse
A reversed list is a chain under relation R if and only if the original list is a chain under the transposed relation (a, b) ↦ R(b, a).
degree_list_kempe_step_symmetric
A degree-list Kempe step is symmetric: if c₂ is obtained from c₁ by swapping colors on a Kempe component, then c₁ is obtained from c₂ by the same swap.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Reversal of degree-list Kempe chains: if α reaches β in k steps, then β reaches α in k steps. -/theorem degree_list_kempe_chain_symm {n : ℕ} (G : SimpleGraph (Fin n))    {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C)    (α β : G.Coloring C) (k : ℕ)    (seq : List (G.Coloring C))    (hne : seq ≠ []) (hhead : seq.head? = some α) (hlast : seq.getLast? = some β)    (hlen : seq.length - 1 = k)    (hchain : seq.IsChain (fun c₁ c₂ => (∀ v, c₁ v ∈ L v) ∧ (∀ v, c₂ v ∈ L v) ∧      ∃ (a b : C) (U : Set (Fin n)),        a ≠ b ∧ U.Nonempty ∧ (∀ v ∈ U, c₁ v = a ∨ c₁ v = b) ∧        (G.induce U).Connected ∧        (∀ u ∈ U, ∀ v : Fin n, 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))) :    ∃ (seq' : List (G.Coloring C)),      seq' ≠ [] ∧ seq'.head? = some β ∧ seq'.getLast? = some α ∧      seq'.length - 1 = k ∧      seq'.IsChain (fun c₁ c₂ => (∀ v, c₁ v ∈ L v) ∧ (∀ v, c₂ v ∈ L v) ∧        ∃ (a b : C) (U : Set (Fin n)),          a ≠ b ∧ U.Nonempty ∧ (∀ v ∈ U, c₁ v = a ∨ c₁ v = b) ∧          (G.induce U).Connected ∧          (∀ u ∈ U, ∀ v : Fin n, 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)) := by  refine ⟨seq.reverse, ?_, ?_, ?_, ?_, ?_⟩  · exact List.reverse_ne_nil_iff.mpr hne  · rw [List.head?_reverse, hlast]  · rw [List.getLast?_reverse, hhead]  · rw [List.length_reverse, hlen]  · rw [List.isChain_reverse]    refine hchain.imp ?_    intro c₁ c₂ h    rcases h with ⟨hL₁, hL₂, a, b, U, hab, hU_ne, hU_colors, hU_conn, hU_closed, hc₂_in, hc₂_out⟩    exact degree_list_kempe_step_symmetric G L c₁ c₂ hL₁ hL₂ a b U hab hU_ne hU_colors hU_conn hU_closed hc₂_in hc₂_out
See it in the graphDiscuss this resultChallenge it