degree_list_kempe_chain_symm
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`).
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.
refine ⟨seq.reverse, ?_, ?_, ?_, ?_, ?_⟩The reversed sequence is non-empty.
Because the original sequence `seq` is non-empty (hypothesis `hne`), its reversal `seq.reverse` is also non-empty.
uses
List.reverse_ne_nil_iff.mpr· exact List.reverse_ne_nil_iff.mpr hneThe 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`.
uses
List.head?_reverse· rw [List.head?_reverse, hlast]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`.
uses
List.getLast?_reverse· rw [List.getLast?_reverse, hhead]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`.
uses
List.length_reverse· rw [List.length_reverse, hlen]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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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