degree_list_kempe_chain_trans
Degree-list Kempe chains are transitive under concatenation: if α can reach γ in k₁ steps and γ can reach β in k₂ steps, then α can reach β in k₁ + k₂ steps.
Statement
theorem degree_list_kempe_chain_trans {n : ℕ} (G : SimpleGraph (Fin n)) {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C) (α γ β : G.Coloring C) (k₁ k₂ : ℕ) (seq₁ seq₂ : List (G.Coloring C)) (h₁_ne : seq₁ ≠ []) (h₁_head : seq₁.head? = some α) (h₁_last : seq₁.getLast? = some γ) (h₁_len : seq₁.length - 1 = k₁) (h₁_chain : 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))) (h₂_ne : seq₂ ≠ []) (h₂_head : seq₂.head? = some γ) (h₂_last : seq₂.getLast? = some β) (h₂_len : seq₂.length - 1 = k₂) (h₂_chain : 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₁ + 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
The proof, explained
To compose two Kempe chains connecting α to γ in k₁ steps and γ to β in k₂ steps, we concatenate the first sequence with the tail of the second sequence, avoiding duplication of the intermediate coloring γ. The non-emptiness, start coloring α, and end coloring β follow directly from the properties of the two component lists. Linear arithmetic establishes that the concatenated sequence has length k₁ + k₂ + 1 (representing k₁ + k₂ steps), and the chain property across the splice point holds because γ transitions to the head of seq₂.tail in the original second sequence.
The candidate sequence is defined by concatenating the first sequence with the tail of the second sequence.
We abbreviate the Kempe step relation as R. Since γ is the head of seq₂, we express seq₂ as γ :: seq₂.tail using List.cons_head?_tail. Dropping the duplicate junction coloring γ, we propose seq₁ ++ seq₂.tail as the witness sequence and reduce the theorem to verifying its five properties: non-emptiness, initial coloring, final coloring, total step count, and the chain condition.
uses
List.cons_head?_taillet R : G.Coloring C → G.Coloring C → Prop := 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) have h₁_chain' : List.IsChain R seq₁ := h₁_chain have h₂_chain' : List.IsChain R seq₂ := h₂_chain have h₂_chain_tail : List.IsChain R seq₂.tail := h₂_chain'.tail have hhead : γ ∈ seq₂.head? := by rw [h₂_head]; simp have hseq₂ : seq₂ = γ :: seq₂.tail := (List.cons_head?_tail hhead).symm refine ⟨seq₁ ++ seq₂.tail, ?_, ?_, ?_, ?_, ?_⟩
The concatenated sequence is nonempty.
Since seq₁ is nonempty by hypothesis (h₁_ne), any list beginning with seq₁ is also nonempty.
· simp [h₁_ne]The head of the concatenated sequence is α.
By List.head?_append, because seq₁ is nonempty, the head of seq₁ ++ seq₂.tail is the head of seq₁, which is α by hypothesis (h₁_head).
uses
List.head?_append· simpa [List.head?_append, h₁_ne] using h₁_headThe last coloring of the concatenated sequence is β.
We case-split on whether seq₂.tail is empty. If it is empty, seq₂ is the single-element list [γ], so γ = β, and the concatenation is just seq₁, whose last element is γ = β. If seq₂.tail is nonempty, List.getLast?_append shows that the last element of the concatenation is the last element of seq₂.tail, which equals the last element of seq₂ (β) by List.getLast?_cons_of_ne_nil.
uses
List.getLast?_append,List.getLast?_cons_of_ne_nil· by_cases ht : seq₂.tail = [] · have hseq₂' : seq₂ = [γ] := by simpa [ht] using hseq₂ have hγβ : γ = β := by simpa [hseq₂'] using h₂_last subst β simpa [ht, h₁_last] · have htail_last : seq₂.tail.getLast? = some β := by rw [hseq₂] at h₂_last simpa [List.getLast?_cons_of_ne_nil ht] using h₂_last simp [List.getLast?_append, h₁_last, htail_last]
The step count of the concatenated sequence is k₁ + k₂.
Since seq₁ and seq₂ are nonempty, their lengths are strictly positive (by List.length_pos_iff.mpr), which implies their lengths are k₁ + 1 and k₂ + 1 respectively. Using List.length_append and List.length_tail, the length of seq₁ ++ seq₂.tail is (k₁ + 1) + k₂ = k₁ + k₂ + 1, so subtracting 1 yields k₁ + k₂.
uses
List.length_pos_iff.mpr,List.length_append,List.length_tail· have h₁pos : 0 < seq₁.length := List.length_pos_iff.mpr h₁_ne have h₂pos : 0 < seq₂.length := List.length_pos_iff.mpr h₂_ne have h₁len' : seq₁.length = k₁ + 1 := by omega have h₂len' : seq₂.length = k₂ + 1 := by omega rw [List.length_append, List.length_tail, h₁len', h₂len'] omega
The concatenated sequence is a valid Kempe chain.
By List.IsChain.append, concatenating the chains seq₁ and seq₂.tail yields a chain provided the Kempe step relation R holds between the last element of seq₁ and the head of seq₂.tail. The last element of seq₁ is γ (by Option.mem_some_iff). Since seq₂ = γ :: seq₂.tail is known to be a chain, List.isChain_cons.mp guarantees that R relates γ to the head of seq₂.tail.
uses
List.IsChain.append,Option.mem_some_iff,List.isChain_cons.mp· apply List.IsChain.append h₁_chain' h₂_chain_tail intro x hx y hy rw [h₁_last] at hx simp only [Option.mem_some_iff] at hx subst x have h2' : List.IsChain R (γ :: seq₂.tail) := by rw [← hseq₂] exact h₂_chain' exact (List.isChain_cons.mp h2').1 y hy
List.cons_head?_tail- If an element is the head of a list, prepending it to the list's tail reconstructs the original list.
List.head?_append- The head of an appended list is the head of the first list if it is nonempty, and the head of the second list otherwise.
List.getLast?_cons_of_ne_nil- The last element of a non-empty tail preceded by an element is simply the last element of that tail.
List.getLast?_append- The last element of an appended list is the last element of the second list if it is nonempty, and the last element of the first list otherwise.
List.length_pos_iff.mpr- A list has strictly positive length if it is nonempty.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_tail- The length of the tail of a list is its length minus one.
List.IsChain.append- Two chains can be concatenated into a single chain if the transition relation holds between the last element of the first chain and the first element of the second chain.
Option.mem_some_iff- An element belongs to `some x` if and only if it equals `x`.
List.isChain_cons.mp- If prepending an element to a list yields a chain, then the element is related to the head of the list (if any) and the list itself is a chain.
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.
/-- Concatenation of degree-list Kempe chains: if α reaches γ in k₁ steps and γ reaches β in k₂ steps, then α reaches β in k₁ + k₂ steps. -/theorem degree_list_kempe_chain_trans {n : ℕ} (G : SimpleGraph (Fin n)) {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C) (α γ β : G.Coloring C) (k₁ k₂ : ℕ) (seq₁ seq₂ : List (G.Coloring C)) (h₁_ne : seq₁ ≠ []) (h₁_head : seq₁.head? = some α) (h₁_last : seq₁.getLast? = some γ) (h₁_len : seq₁.length - 1 = k₁) (h₁_chain : 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))) (h₂_ne : seq₂ ≠ []) (h₂_head : seq₂.head? = some γ) (h₂_last : seq₂.getLast? = some β) (h₂_len : seq₂.length - 1 = k₂) (h₂_chain : 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₁ + 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 let R : G.Coloring C → G.Coloring C → Prop := 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) have h₁_chain' : List.IsChain R seq₁ := h₁_chain have h₂_chain' : List.IsChain R seq₂ := h₂_chain have h₂_chain_tail : List.IsChain R seq₂.tail := h₂_chain'.tail have hhead : γ ∈ seq₂.head? := by rw [h₂_head]; simp have hseq₂ : seq₂ = γ :: seq₂.tail := (List.cons_head?_tail hhead).symm refine ⟨seq₁ ++ seq₂.tail, ?_, ?_, ?_, ?_, ?_⟩ · simp [h₁_ne] · simpa [List.head?_append, h₁_ne] using h₁_head · by_cases ht : seq₂.tail = [] · have hseq₂' : seq₂ = [γ] := by simpa [ht] using hseq₂ have hγβ : γ = β := by simpa [hseq₂'] using h₂_last subst β simpa [ht, h₁_last] · have htail_last : seq₂.tail.getLast? = some β := by rw [hseq₂] at h₂_last simpa [List.getLast?_cons_of_ne_nil ht] using h₂_last simp [List.getLast?_append, h₁_last, htail_last] · have h₁pos : 0 < seq₁.length := List.length_pos_iff.mpr h₁_ne have h₂pos : 0 < seq₂.length := List.length_pos_iff.mpr h₂_ne have h₁len' : seq₁.length = k₁ + 1 := by omega have h₂len' : seq₂.length = k₂ + 1 := by omega rw [List.length_append, List.length_tail, h₁len', h₂len'] omega · apply List.IsChain.append h₁_chain' h₂_chain_tail intro x hx y hy rw [h₁_last] at hx simp only [Option.mem_some_iff] at hx subst x have h2' : List.IsChain R (γ :: seq₂.tail) := by rw [← hseq₂] exact h₂_chain' exact (List.isChain_cons.mp h2').1 y hy