AFTD Auto-Formalizing Theoretical Domains

degree_list_kempe_step_symmetric

theoremverified

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

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.

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

    line 19

      refine ⟨hL₂, hL₁, a, b, U, hab, hU_ne, ?_, hU_conn, ?_, ?_, ?_⟩
  2. 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}.

    lines 20–24

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

    lines 25–28

      · 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)
  4. 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).

    lines 29–38

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

    lines 39–40

      · 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

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