degree_list_kempe_single_vertex_diff
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.
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.
uses
List.isChain_consrefine ⟨[α, β], by simp, by simp, by simp, by simp, ?_⟩ rw [List.isChain_cons] refine ⟨?_, by simp⟩
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.
uses
List.head?_cons,Option.mem_some_iff,Set.singleton_nonemptyintro 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₀, ?_, ?_, ?_, ?_, ?_⟩
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₀).
uses
Set.mem_singleton_iff.mp,Or.inl· intro v hv rw [Set.mem_singleton_iff.mp hv] exact Or.inl rfl
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.
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
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.
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)
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₀).
uses
Set.mem_singleton_iff.mp· intro v hv rw [Set.mem_singleton_iff.mp hv] simp
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).
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.
- Basic properties of lists (non-emptiness, length arithmetic, head and last element, and the chain condition on a singleton list) are closed directly by simplification.
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.
/-- 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