AFTD Auto-Formalizing Theoretical Domains

degree_list_kempe_chain_trans

theoremverified

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.

  1. 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.

    lines 34–47

    uses List.cons_head?_tail

      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, ?_, ?_, ?_, ?_, ?_⟩
  2. The concatenated sequence is nonempty.

    Since seq₁ is nonempty by hypothesis (h₁_ne), any list beginning with seq₁ is also nonempty.

    line 48

      · simp [h₁_ne]
  3. 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).

    line 49

    uses List.head?_append

      · simpa [List.head?_append, h₁_ne] using h₁_head
  4. The 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.

    lines 50–58

    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]
  5. 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₂.

    lines 59–64

    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
  6. 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.

    lines 65–73

    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

/-- 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
See it in the graphDiscuss this resultChallenge it