degree_list_kempe_step_symmetric
The 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 on an induced connected component U, then c₁ is obtained from c₂ by an L-valid Kempe change swapping the same colors on the same component U.
Statement
theorem degree_list_kempe_step_symmetric {n : ℕ} (G : SimpleGraph (Fin n)) {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C) (c₁ c₂ : G.Coloring C) (hL₁ : ∀ v, c₁ v ∈ L v) (hL₂ : ∀ v, c₂ v ∈ L v) (a b : C) (U : Set (Fin n)) (hab : a ≠ b) (hU_ne : U.Nonempty) (hU_colors : ∀ v ∈ U, c₁ v = a ∨ c₁ v = b) (hU_conn : (G.induce U).Connected) (hU_closed : ∀ u ∈ U, ∀ v : Fin n, G.Adj u v → (c₁ v = a ∨ c₁ v = b) → v ∈ U) (hc₂_in : ∀ v ∈ U, c₂ v = (if c₁ v = a then b else a)) (hc₂_out : ∀ v ∉ U, c₂ v = c₁ v) : (∀ 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- Used by 1
- degree_list_kempe_chain_symmReversal of degree-list Kempe chains: if α can reach β in k steps, then β can reach α in k steps.
The proof, explained
The proof shows that the Kempe transition relation is symmetric by witnessing that c₁ can be obtained from c₂ using the exact same two colors a, b and the same component U. Swapping colors a and b is an involution on {a, b}, so on U the colors under c₂ remain in {a, b} and swapping them a second time restores c₁. Outside U, the vertices retain their colors from c₁, ensuring that the neighborhood closure condition defining the Kempe component is preserved.
To show that c₁ is obtainable from c₂ by a Kempe change, it suffices to use the same colors a and b and the same component U.
We supply a, b, and U as the witnesses for the reverse Kempe change from c₂ to c₁. The list-coloring conditions for both c₂ and c₁, the inequality a ≠ b, the nonemptiness of U, and the connectedness of the induced subgraph G[U] are all provided directly by the hypotheses. This leaves four subgoals: showing that c₂ takes only colors a and b on U, that U is closed under (a, b)-colored neighbors under c₂, that swapping colors in c₂ recovers c₁ on U, and that c₁ and c₂ agree outside U.
refine ⟨hL₂, hL₁, a, b, U, hab, hU_ne, ?_, hU_conn, ?_, ?_, ?_⟩On the component U, every vertex has color a or b under c₂.
For any vertex v ∈ U, c₁(v) is either a or b. If c₁(v) = a, then the Kempe swap rule (hc₂_in) sets c₂(v) = b. If c₁(v) = b, then since a ≠ b, c₁(v) ≠ a, so the Kempe swap sets c₂(v) = a. In either case, c₂(v) ∈ {a, b}.
uses
if_pos,Or.inr,if_neg,Or.inl· intro v hv rcases hU_colors v hv with h1 | h1 · rw [hc₂_in v hv, if_pos h1]; exact Or.inr rfl · rw [hc₂_in v hv, if_neg (fun hc => hab (hc.symm.trans h1))] exact Or.inl rfl
The component U is closed under neighbors colored a or b in c₂: if u ∈ U is adjacent to v and c₂(v) ∈ {a, b}, then v ∈ U.
Assume for contradiction that v ∉ U. Since v is outside U, the coloring is unchanged between c₁ and c₂ (by hc₂_out), so c₁(v) = c₂(v) ∈ {a, b}. Since u ∈ U and v is a neighbor of u, the closure of U under c₁ (hU_closed) implies v ∈ U, contradicting v ∉ U.
· intro u hu v hadj hv by_contra hvu rw [hc₂_out v hvu] at hv exact hvu (hU_closed u hu v hadj hv)
On U, swapping colors a and b in c₂ recovers the coloring c₁.
For any v ∈ U, we split into cases based on whether c₁(v) = a. If c₁(v) = a, then c₂(v) = b; since b ≠ a, swapping colors on c₂(v) gives a, which is c₁(v). If c₁(v) ≠ a, then because c₁(v) ∈ {a, b}, we must have c₁(v) = b; then c₂(v) = a, and swapping colors on c₂(v) gives b, which is c₁(v).
uses
if_pos,if_neg· intro v hv by_cases h1 : c₁ v = a · have : c₂ v = b := by rw [hc₂_in v hv, if_pos h1] rw [this, if_neg (fun hba => hab hba.symm), h1] · have h2 : c₁ v = b := by rcases hU_colors v hv with h | h · exact absurd h h1 · exact h have : c₂ v = a := by rw [hc₂_in v hv, if_neg h1] rw [this, if_pos rfl, h2]
Outside U, the coloring c₁ agrees with c₂.
For any vertex v ∉ U, the hypothesis hc₂_out gives c₂(v) = c₁(v). By symmetry of equality, c₁(v) = c₂(v).
· intro v hv exact (hc₂_out v hv).symm
if_pos- If the condition c is true, then the conditional if c then t else e evaluates to t.
if_neg- If the condition c is false (¬c), then the conditional if c then t else e evaluates to e.
Or.inl- From a proof of the left disjunct a, concludes the disjunction a ∨ b.
Or.inr- From a proof of the right disjunct b, concludes the disjunction a ∨ b.
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.
/-- The degree-list Kempe step transition relation is symmetric: swapping colors a and b on an induced connected component U is an involution. -/theorem degree_list_kempe_step_symmetric {n : ℕ} (G : SimpleGraph (Fin n)) {C : Type} [Fintype C] [DecidableEq C] (L : Fin n → Finset C) (c₁ c₂ : G.Coloring C) (hL₁ : ∀ v, c₁ v ∈ L v) (hL₂ : ∀ v, c₂ v ∈ L v) (a b : C) (U : Set (Fin n)) (hab : a ≠ b) (hU_ne : U.Nonempty) (hU_colors : ∀ v ∈ U, c₁ v = a ∨ c₁ v = b) (hU_conn : (G.induce U).Connected) (hU_closed : ∀ u ∈ U, ∀ v : Fin n, G.Adj u v → (c₁ v = a ∨ c₁ v = b) → v ∈ U) (hc₂_in : ∀ v ∈ U, c₂ v = (if c₁ v = a then b else a)) (hc₂_out : ∀ v ∉ U, c₂ v = c₁ v) : (∀ 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 ⟨hL₂, hL₁, a, b, U, hab, hU_ne, ?_, hU_conn, ?_, ?_, ?_⟩ · intro v hv rcases hU_colors v hv with h1 | h1 · rw [hc₂_in v hv, if_pos h1]; exact Or.inr rfl · rw [hc₂_in v hv, if_neg (fun hc => hab (hc.symm.trans h1))] exact Or.inl rfl · intro u hu v hadj hv by_contra hvu rw [hc₂_out v hvu] at hv exact hvu (hU_closed u hu v hadj hv) · intro v hv by_cases h1 : c₁ v = a · have : c₂ v = b := by rw [hc₂_in v hv, if_pos h1] rw [this, if_neg (fun hba => hab hba.symm), h1] · have h2 : c₁ v = b := by rcases hU_colors v hv with h | h · exact absurd h h1 · exact h have : c₂ v = a := by rw [hc₂_in v hv, if_neg h1] rw [this, if_pos rfl, h2] · intro v hv exact (hc₂_out v hv).symm