AFTD Auto-Formalizing Theoretical Domains

degree_list_kempe_single_vertex_diff

theoremverified

If two proper L-colorings α and β differ at exactly one vertex v₀, then β is reachable from α in a single L-valid Kempe change on the singleton component U = {v₀}.

Statement

theorem degree_list_kempe_single_vertex_diff {n : ℕ} (G : SimpleGraph (Fin n))
    {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C)
    (α β : G.Coloring C)
    (hLα : ∀ v, α v ∈ L v) (hLβ : ∀ v, β v ∈ L v)
    (v₀ : Fin n) (h_diff : ∀ v, v ≠ v₀ → α v = β v) (hne : α v₀ ≠ β v₀) :
    ∃ (seq : List (G.Coloring C)),
      seq ≠ [] ∧ seq.head? = some α ∧ seq.getLast? = some β ∧
      seq.length - 1 = 1 ∧
      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

The proof shows that β is reachable from α via a 1-step Kempe sequence by proposing the two-element list [α, β]. Choosing U = {v₀} and the two colors to be α(v₀) and β(v₀), the singleton component is trivially non-empty and connected. Component maximality holds because any neighbor v of v₀ differs from v₀, so α(v) = β(v), preventing v from having color α(v₀) (by properness of α) or β(v₀) (by properness of β). Finally, swapping the color at v₀ produces β(v₀) while leaving all other vertex colors unchanged.

  1. The sequence [α, β] satisfies all required list structure conditions, reducing the goal to showing that (α, β) is a valid Kempe transition.

    We choose the two-coloring sequence [α, β]. Its non-emptiness, length condition (2 - 1 = 1), head (α), and last element (β) are all verified by list simplification. Using List.isChain_cons to unfold the chain condition, the singleton tail [β] is vacuously a chain, leaving only the requirement that α and β form a valid Kempe transition.

    lines 17–19

    uses List.isChain_cons

      refine ⟨[α, β], by simp, by simp, by simp, by simp, ?_⟩
      rw [List.isChain_cons]
      refine ⟨?_, by simp⟩
  2. The Kempe transition from α to β is instantiated with component U = {v₀} and colors a = α(v₀), b = β(v₀).

    Unpacking the head of [β] identifies the target coloring y with β. We instantiate the Kempe step with colors α(v₀) and β(v₀), and component U = {v₀}. The color-list memberships hold by hypotheses hLα and hLβ, the colors are distinct by hne (α(v₀) ≠ β(v₀)), and {v₀} is non-empty by Set.singleton_nonempty. Five conditions remain: component color restriction, connectedness, component maximality, color exchange on U, and constancy outside U.

    lines 20–23

    uses List.head?_cons, Option.mem_some_iff, Set.singleton_nonempty

      intro y hy
      simp only [List.head?_cons, Option.mem_some_iff] at hy
      subst hy
      refine ⟨hLα, hLβ, α v₀, β v₀, {v₀}, hne, Set.singleton_nonempty v₀, ?_, ?_, ?_, ?_, ?_⟩
  3. Every vertex in U = {v₀} has color α(v₀) or β(v₀) under α.

    Any vertex v in the singleton set {v₀} equals v₀. Its color under α is therefore α(v₀), which satisfies the left disjunct of α(v) = α(v₀) ∨ α(v) = β(v₀).

    lines 24–26

    uses Set.mem_singleton_iff.mp, Or.inl

      · intro v hv
        rw [Set.mem_singleton_iff.mp hv]
        exact Or.inl rfl
  4. The induced subgraph G[U] on the singleton U = {v₀} is connected.

    Any two vertices in the induced subgraph must both be the single vertex v₀. Reachability from v₀ to itself holds reflexively.

    lines 27–32

    uses Set.mem_singleton_iff.mp

      · constructor
        · rintro ⟨u, hu⟩ ⟨v, hv⟩
          have hu' : u = v₀ := Set.mem_singleton_iff.mp hu
          have hv' : v = v₀ := Set.mem_singleton_iff.mp hv
          subst hu' hv'
          rfl
  5. The component U = {v₀} is maximal: no neighbor of v₀ has color α(v₀) or β(v₀) under α.

    Let v be any neighbor of v₀. Since G is a simple graph, v ≠ v₀, so α(v) = β(v) by hypothesis h_diff. Because α is a proper coloring, adjacent vertices have different colors, so α(v) ≠ α(v₀). Similarly, because β is a proper coloring, β(v) ≠ β(v₀), which means α(v) ≠ β(v₀). Hence α(v) can be neither α(v₀) nor β(v₀), deriving a contradiction via False.elim and confirming that no neighbor of v₀ belongs to U.

    lines 33–43

    uses Set.mem_singleton_iff.mp, False.elim

      · intro u hu v hadj hcol
        rw [Set.mem_singleton_iff.mp hu] at hadj
        have hne_v : v ≠ v₀ := hadj.ne'
        have hcol_v : α v = β v := h_diff v hne_v
        have hneq_a : α v ≠ α v₀ := α.valid hadj.symm
        have hneq_b : α v ≠ β v₀ := by
          rw [hcol_v]
          exact β.valid hadj.symm
        cases hcol with
        | inl ha => exact False.elim (hneq_a ha)
        | inr hb => exact False.elim (hneq_b hb)
  6. On U = {v₀}, the coloring β correctly swaps the color α(v₀) to β(v₀).

    For the single vertex v₀ in U, the swap rule requires β(v₀) = (if α(v₀) = α(v₀) then β(v₀) else α(v₀)). Since the equality α(v₀) = α(v₀) holds reflexively, the conditional simplifies directly to β(v₀).

    lines 44–46

    uses Set.mem_singleton_iff.mp

      · intro v hv
        rw [Set.mem_singleton_iff.mp hv]
        simp
  7. Outside U = {v₀}, the colorings α and β agree.

    Any vertex v not in {v₀} satisfies v ≠ v₀ by contraposition (mt). By the hypothesis h_diff that α and β agree on all vertices other than v₀, we obtain α(v) = β(v), which gives β(v) = α(v).

    lines 47–49

    uses mt, Set.mem_singleton_iff.mp

      · intro v hv
        have hne_v : v ≠ v₀ := mt Set.mem_singleton_iff.mp hv
        exact (h_diff v hne_v).symm
List.isChain_cons
A non-empty list x :: l is a chain under relation R if and only if R x y holds for the head y of l (if any) and l is itself a chain under R.
List.head?_cons
The head of a non-empty list a :: l is some a.
Option.mem_some_iff
An element a belongs to some b if and only if b = a.
Set.singleton_nonempty
The singleton set {a} is non-empty.
Set.mem_singleton_iff.mp
If an element belongs to the singleton set {x}, then it equals x.
Or.inl
Proof of a disjunction from a proof of its left conjunct: a implies a ∨ b.
False.elim
Principle of explosion: from False, any proposition follows.
mt
Modus tollens: if a implies b, then ¬b implies ¬a.

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

/-- Two proper L-colorings differing on a single vertex are connected by a 1-step Kempe change. -/theorem degree_list_kempe_single_vertex_diff {n : ℕ} (G : SimpleGraph (Fin n))    {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C)    (α β : G.Coloring C)    (hLα : ∀ v, α v ∈ L v) (hLβ : ∀ v, β v ∈ L v)    (v₀ : Fin n) (h_diff : ∀ v, v ≠ v₀ → α v = β v) (hne : α v₀ ≠ β v₀) :    ∃ (seq : List (G.Coloring C)),      seq ≠ [] ∧ seq.head? = some α ∧ seq.getLast? = some β ∧      seq.length - 1 = 1 ∧      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 ⟨[α, β], by simp, by simp, by simp, by simp, ?_⟩  rw [List.isChain_cons]  refine ⟨?_, by simp⟩  intro y hy  simp only [List.head?_cons, Option.mem_some_iff] at hy  subst hy  refine ⟨hLα, hLβ, α v₀, β v₀, {v₀}, hne, Set.singleton_nonempty v₀, ?_, ?_, ?_, ?_, ?_⟩  · intro v hv    rw [Set.mem_singleton_iff.mp hv]    exact Or.inl rfl  · constructor    · rintro ⟨u, hu⟩ ⟨v, hv⟩      have hu' : u = v₀ := Set.mem_singleton_iff.mp hu      have hv' : v = v₀ := Set.mem_singleton_iff.mp hv      subst hu' hv'      rfl  · intro u hu v hadj hcol    rw [Set.mem_singleton_iff.mp hu] at hadj    have hne_v : v ≠ v₀ := hadj.ne'    have hcol_v : α v = β v := h_diff v hne_v    have hneq_a : α v ≠ α v₀ := α.valid hadj.symm    have hneq_b : α v ≠ β v₀ := by      rw [hcol_v]      exact β.valid hadj.symm    cases hcol with    | inl ha => exact False.elim (hneq_a ha)    | inr hb => exact False.elim (hneq_b hb)  · intro v hv    rw [Set.mem_singleton_iff.mp hv]    simp  · intro v hv    have hne_v : v ≠ v₀ := mt Set.mem_singleton_iff.mp hv    exact (h_diff v hne_v).symm
See it in the graphDiscuss this resultChallenge it