AFTD Auto-Formalizing Theoretical Domains

simple_graph_reconfiguration_frozen_core_reachable_eq

theoremverifiedformalization

Let G be a simple graph, s a subset of vertices, and α a proper k-coloring of G whose restriction to the induced subgraph on s is frozen with respect to all k colors. Then every coloring β reachable from α in the k-reconfiguration graph of G agrees with α on s.

Statement

theorem simple_graph_reconfiguration_frozen_core_reachable_eq
    {V : Type*} (G : SimpleGraph V) {k : ℕ} (s : Set V)
    (α β : G.Coloring (Fin k))
    (hfrozen : ∀ (x : V), x ∈ s → ∀ (i : Fin k), α x = i ∨ ∃ y ∈ s, G.Adj x y ∧ α y = i)
    (hreach : (simple_graph_reconfiguration_graph G k).Reachable α β) :
    ∀ x ∈ s, β x = α x
Formalizes
arXiv:2610.27527 Lemma 2.3
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

Read back from the Lean

For any type $V$, simple graph $G$ on $V$, natural number $k$, subset $s \subseteq V$, and proper colorings $\alpha, \beta$ of $G$ with colors in $\mathrm{Fin}(k)$: Assume that: 1. For every vertex $x \in s$ and every color $i \in \mathrm{Fin}(k)$, either $\alpha(x) = i$ or there exists some $y \in s$ such that $x$ and $y$ are adjacent in $G$ and $\alpha(y) = i$. 2. $\beta$ is reachable from $\alpha$ in the reconfiguration graph of proper $k$-colorings of $G$, where two proper $k$-colorings are adjacent if and only if they differ at exactly one vertex. Then for every vertex $x \in s$, $\beta(x) = \alpha(x)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by induction on the length of a reconfiguration sequence from α to β, showing that every step preserves the coloring on s. At each step, exactly one vertex v changes color; because α is frozen on s, recoloring any vertex in s would either leave its color unchanged or create a monochromatic edge with a neighbor in s, so the recolored vertex v must lie outside s. Since vertices in s are never recolored, every reachable coloring β agrees with α on s.

  1. To establish that agreement with α on s is preserved under reconfiguration, consider adjacent colorings c₁ and c₂ with c₁ = α on s, differing at a unique vertex v.

    We state the invariant `hstep`: if c₁ and c₂ are adjacent in the reconfiguration graph and c₁ agrees with α on s, then c₂ also agrees with α on s. By definition of adjacency in the reconfiguration graph, c₁ and c₂ differ at exactly one vertex v, so c₁(v) ≠ c₂(v) and c₁(y) = c₂(y) for all y ≠ v.

    lines 8–12

      have hstep : ∀ {c₁ c₂ : G.Coloring (Fin k)},
          (simple_graph_reconfiguration_graph G k).Adj c₁ c₂ →
          (∀ x ∈ s, c₁ x = α x) → (∀ x ∈ s, c₂ x = α x) := by
        intro c₁ c₂ hadj hc₁
        obtain ⟨v, hv, huniq⟩ := hadj
  2. The recolored vertex v cannot belong to s (v ∉ s).

    Suppose for contradiction that v ∈ s. By the frozen hypothesis for v and the target color c₂(v), there are two possibilities: either α(v) = c₂(v), or there is some neighbor y ∈ s of v such that α(y) = c₂(v). In the first case, since c₁ agrees with α on s, c₁(v) = α(v) = c₂(v), which contradicts c₁(v) ≠ c₂(v). In the second case, because y is adjacent to v, y ≠ v, and therefore c₁(y) = c₂(y). Hence c₂(y) = c₁(y) = α(y) = c₂(v), meaning the adjacent vertices y and v share the same color under c₂, contradicting that c₂ is a proper coloring. Thus v ∉ s.

    lines 13–27

        have hv_notin_s : v ∉ s := by
          intro hvs
          have hcases := hfrozen v hvs (c₂ v)
          rcases hcases with h1 | ⟨y, hys, hadj_vy, hy_col⟩
          · rw [← hc₁ v hvs] at h1
            exact hv h1
          · have hne : y ≠ v := hadj_vy.ne'
            have hc12 : c₁ y = c₂ y := by
              by_contra hne'
              exact hne (huniq y hne')
            have hc2y : c₂ y = c₂ v := by
              calc c₂ y = c₁ y := hc12.symm
              _ = α y := hc₁ y hys
              _ = c₂ v := hy_col
            exact c₂.valid hadj_vy (hc2y.symm)
  3. Single reconfiguration steps preserve agreement with α on s (`hstep`).

    For any vertex x ∈ s, since v ∉ s, we have x ≠ v. Because v is the unique vertex where c₁ and c₂ differ, c₂(x) = c₁(x). Since c₁ agrees with α on s, c₁(x) = α(x), and therefore c₂(x) = α(x). This finishes the proof of `hstep`.

    lines 28–33

        intro x hxs
        have hxne : x ≠ v := fun h => hv_notin_s (h ▸ hxs)
        have hc12 : c₁ x = c₂ x := by
          by_contra hne'
          exact hxne (huniq x hne')
        rw [← hc12, hc₁ x hxs]
  4. Every coloring β reachable from α agrees with α on s.

    We rewrite reachability in the reconfiguration graph as the reflexive-transitive closure of single-step adjacency via `SimpleGraph.reachable_iff_reflTransGen`. By induction on this relation: in the base case where β = α, the colorings trivially agree on s; in the inductive step, `hstep` ensures that agreement on s is preserved across each transition.

    lines 34–37

    uses SimpleGraph.reachable_iff_reflTransGen

      rw [SimpleGraph.reachable_iff_reflTransGen] at hreach
      induction hreach with
      | refl => intro x _; rfl
      | tail _ hadj ih => exact hstep hadj ih
SimpleGraph.reachable_iff_reflTransGen
Two vertices in a simple graph are reachable from each other if and only if they are related by the reflexive-transitive closure of the graph's adjacency relation.

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

/-- Every coloring reachable in the k-reconfiguration graph from a coloring that is frozen on an induced subgraph agrees with it on that subgraph. -/theorem simple_graph_reconfiguration_frozen_core_reachable_eq    {V : Type*} (G : SimpleGraph V) {k : ℕ} (s : Set V)    (α β : G.Coloring (Fin k))    (hfrozen : ∀ (x : V), x ∈ s → ∀ (i : Fin k), α x = i ∨ ∃ y ∈ s, G.Adj x y ∧ α y = i)    (hreach : (simple_graph_reconfiguration_graph G k).Reachable α β) :    ∀ x ∈ s, β x = α x := by  have hstep : ∀ {c₁ c₂ : G.Coloring (Fin k)},      (simple_graph_reconfiguration_graph G k).Adj c₁ c₂ →      (∀ x ∈ s, c₁ x = α x) → (∀ x ∈ s, c₂ x = α x) := by    intro c₁ c₂ hadj hc₁    obtain ⟨v, hv, huniq⟩ := hadj    have hv_notin_s : v ∉ s := by      intro hvs      have hcases := hfrozen v hvs (c₂ v)      rcases hcases with h1 | ⟨y, hys, hadj_vy, hy_col⟩      · rw [← hc₁ v hvs] at h1        exact hv h1      · have hne : y ≠ v := hadj_vy.ne'        have hc12 : c₁ y = c₂ y := by          by_contra hne'          exact hne (huniq y hne')        have hc2y : c₂ y = c₂ v := by          calc c₂ y = c₁ y := hc12.symm          _ = α y := hc₁ y hys          _ = c₂ v := hy_col        exact c₂.valid hadj_vy (hc2y.symm)    intro x hxs    have hxne : x ≠ v := fun h => hv_notin_s (h ▸ hxs)    have hc12 : c₁ x = c₂ x := by      by_contra hne'      exact hxne (huniq x hne')    rw [← hc12, hc₁ x hxs]  rw [SimpleGraph.reachable_iff_reflTransGen] at hreach  induction hreach with  | refl => intro x _; rfl  | tail _ hadj ih => exact hstep hadj ih
See it in the graphDiscuss this resultChallenge it