simple_graph_reconfiguration_frozen_core_reachable_eq
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
- simple_graph_reconfiguration_graphFor a simple graph G and a natural number k, the k-reconfiguration graph of G is the simple graph whose vertices are the proper…
- Used by 1
- simple_graph_reconfiguration_not_connected_of_frozen_subgraphIf a simple graph G admits a proper ℓ-coloring α whose restriction to a nonempty subset S is frozen with respect to all ℓ colors, and G…
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.
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.
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
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.
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)
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`.
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]
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.
uses
SimpleGraph.reachable_iff_reflTransGenrw [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
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.
/-- 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