simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite
Let G be a finite bipartite simple graph on a type V with decidable equality and decidable adjacency. For every integer k ≥ G.maxDegree + 2 and any two proper k-colourings α and β of G with colours in Fin k, there exists a walk in the k-colouring reconfiguration graph of G from α to β of length at most 3 * Fintype.card V / 2.
Statement
theorem simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) {k : ℕ} (hk : G.maxDegree + 2 ≤ k) (α β : G.Coloring (Fin k)) : ∃ w : (simple_graph_reconfiguration_graph G k).Walk α β, w.length ≤ 3 * Fintype.card V / 2
- Source
- arXiv:2611.17022 Lemma 6 -- Large diameter for (Δ+2)-colouring reconfiguration
- Verified
- 15 Nov 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_diam_le_three_halves_of_bipartiteLet G be a finite bipartite simple graph on a type V with decidable equality and decidable adjacency. For every integer k ≥ G.maxDegree +…
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Assume that $G$ is bipartite. Let $k$ be a natural number such that $G.\mathrm{maxDegree} + 2 \le k$. For any two proper $k$-colorings $\alpha$ and $\beta$ of $G$ (with colors in $\mathrm{Fin}(k)$), there exists a walk $w$ from $\alpha$ to $\beta$ in the coloring reconfiguration graph of $G$ with $k$ colors (where two proper colorings are adjacent if and only if they differ at exactly one vertex of $V$) such that the length of $w$ is at most $\lfloor 3 |V| / 2 \rfloor$ (using natural number division 3 * Fintype.card V / 2).
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
To reconfigure between any two proper k-colourings α and β of a bipartite graph G with partition V = A ⊔ B when k ≥ Δ(G) + 2, the proof establishes a five-phase routing lemma using a pivot colour c. The five phases clear colour c from B, colour all of A with c, recolour B towards β while parking vertices needing colour c at temporary free colours, recolour A to β, and finally unpark B. This construction bounds the walk length in terms of |A|, |B|, and the occurrences of colour c in each part. Applying this routing symmetrically to both (A, B) and (B, A) causes all colour-count terms to cancel, proving that the sum of the two walk lengths is at most 3|V| and hence the shorter walk has length at most ⌊3|V|/2⌋.
In rc32_assign, the claim holds when the independent set s is empty via the trivial walk of length 0.
We induct on the finite set s using Finset.induction_on. When s = ∅, no vertices need recolouring; setting γ' = γ and taking the empty walk SimpleGraph.Walk.nil trivially satisfies the length bound 0 ≤ 0.
uses
Finset.induction_on,SimpleGraph.Walk.niltheorem rc32_assign {V : Type*} [DecidableEq V] (G : SimpleGraph V) (k : ℕ) (g : V → Fin k) (s : Finset V) (hs : ∀ v ∈ s, ∀ w ∈ s, ¬ G.Adj v w) : ∀ γ : G.Coloring (Fin k), (∀ v ∈ s, ∀ w, G.Adj v w → g v ≠ γ w) → ∃ γ' : G.Coloring (Fin k), (∀ v, γ' v = if v ∈ s then g v else γ v) ∧ ∃ w : (simple_graph_reconfiguration_graph G k).Walk γ γ', w.length ≤ (s.filter (fun v => γ v ≠ g v)).card := by induction s using Finset.induction_on with | empty => intro γ _ exact ⟨γ, fun v => by simp, SimpleGraph.Walk.nil, by simp⟩
In rc32_assign for s = {a} ∪ s', if γ(a) already equals g(a), the walk obtained for s' by induction suffices.
We apply the induction hypothesis to s', obtaining a walk w1 to a colouring γ1 matching g on s'. Because γ(a) = g(a), vertex a already has its target colour in γ1, and the length of w1 is bounded by the number of differing vertices in s', which is at most that in {a} ∪ s'.
uses
Finset.mem_insert_of_mem,Finset.card_le_card,Finset.filter_subset_filter,Finset.subset_insert| @insert a s ha ih => intro γ hval have hs' : ∀ v ∈ s, ∀ w ∈ s, ¬ G.Adj v w := fun v hv w hw => hs v (Finset.mem_insert_of_mem hv) w (Finset.mem_insert_of_mem hw) obtain ⟨γ1, h1, w1, hw1⟩ := ih hs' γ (fun v hv w hvw => hval v (Finset.mem_insert_of_mem hv) w hvw) have hcard : (s.filter (fun v => γ v ≠ g v)).card ≤ ((insert a s).filter (fun v => γ v ≠ g v)).card := Finset.card_le_card (Finset.filter_subset_filter _ (Finset.subset_insert _ _)) by_cases hga : γ a = g a · refine ⟨γ1, fun v => ?_, w1, hw1.trans hcard⟩ rw [h1 v] by_cases hv : v = a · subst hv simp [ha, hga] · simp [hv]When γ(a) ≠ g(a), updating γ1 at vertex a to g(a) produces a valid proper colouring γ2.
Because {a} ∪ s' is an independent set, no neighbour w of a lies in s', so neighbours of a retain their original colour from γ. The hypothesis on g guarantees that g(a) differs from γ(w) for all neighbours w. Thus updating γ1 at a to g(a) introduces no monochromatic edges, defining a valid proper colouring γ2 via SimpleGraph.Coloring.mk.
uses
Finset.mem_insert_self,Finset.mem_insert_of_mem,if_neg,SimpleGraph.Coloring.mk,Function.update_self,Function.update_of_ne· have hnbr : ∀ w, G.Adj a w → g a ≠ γ1 w := by intro w haw have hw : w ∉ s := fun hw => hs a (Finset.mem_insert_self _ _) w (Finset.mem_insert_of_mem hw) haw rw [h1 w, if_neg hw] exact hval a (Finset.mem_insert_self _ _) w haw let γ2 : G.Coloring (Fin k) := SimpleGraph.Coloring.mk (Function.update γ1 a (g a)) (by intro x y hxy by_cases hx : x = a · subst hx have hy : y ≠ x := fun h => by subst h; exact G.irrefl hxy rw [Function.update_self, Function.update_of_ne hy] exact hnbr y hxy · by_cases hy : y = a · subst hy rw [Function.update_self, Function.update_of_ne hx] exact (hnbr x hxy.symm).symm · rw [Function.update_of_ne hx, Function.update_of_ne hy] exact γ1.valid hxy)
Extending w1 by the single step from γ1 to γ2 completes the induction step of rc32_assign.
The colouring γ2 differs from γ1 only at vertex a, which forms an edge in the reconfiguration graph. Concatenating this step to w1 increases its length by 1, matching the increase in differing vertices since γ(a) ≠ g(a).
uses
if_neg,Function.update_self,Function.update_of_ne,SimpleGraph.Walk.length_concat,Finset.filter_insert,if_pos,Finset.card_insert_of_notMemhave hγ2 : ∀ v, γ2 v = Function.update γ1 a (g a) v := fun v => rfl have hγ1a : γ1 a = γ a := by rw [h1 a, if_neg ha] have hadj : (simple_graph_reconfiguration_graph G k).Adj γ1 γ2 := by refine ⟨a, ?_, ?_⟩ · show γ1 a ≠ γ2 a rw [hγ2, Function.update_self, hγ1a] exact hga · intro u hu change γ1 u ≠ γ2 u at hu by_contra hua exact hu (by rw [hγ2, Function.update_of_ne hua]) refine ⟨γ2, fun v => ?_, w1.concat hadj, ?_⟩ · rw [hγ2] by_cases hv : v = a · subst hv simp · rw [Function.update_of_ne hv, h1 v] simp [hv] · rw [SimpleGraph.Walk.length_concat, Finset.filter_insert, if_pos hga, Finset.card_insert_of_notMem (by simp [ha])] omega
When k ≥ Δ(G) + 2, for every vertex v, colour c, and colouring f, there exists an available colour x ≠ c not used on any neighbour of v (lemma rc32_free).
The forbidden set {c} ∪ f(N(v)) has cardinality at most 1 + deg(v) ≤ 1 + Δ(G) < k. Since the total number of colours k is strictly larger than the size of the forbidden set, the pigeonhole principle (Finset.exists_mem_notMem_of_card_lt_card) provides a colour x not in the forbidden set, so x ≠ c and f(w) ≠ x for all neighbours w of v.
uses
Finset.card_univ,Fintype.card_fin,Finset.card_insert_le,Nat.add_le_add_right,Finset.card_image_le,Finset.exists_mem_notMem_of_card_lt_card,Finset.mem_insert_self,Finset.mem_insert_of_memtheorem rc32_free {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : G.maxDegree + 2 ≤ k) (f : V → Fin k) (c : Fin k) (v : V) : ∃ x : Fin k, x ≠ c ∧ ∀ w, G.Adj v w → f w ≠ x := by have hlt : (insert c ((G.neighborFinset v).image f)).card < (Finset.univ : Finset (Fin k)).card := by rw [Finset.card_univ, Fintype.card_fin] calc (insert c ((G.neighborFinset v).image f)).card ≤ ((G.neighborFinset v).image f).card + 1 := Finset.card_insert_le _ _ _ ≤ (G.neighborFinset v).card + 1 := Nat.add_le_add_right Finset.card_image_le _ _ ≤ G.maxDegree + 1 := by rw [G.card_neighborFinset_eq_degree] exact Nat.add_le_add_right (G.degree_le_maxDegree v) _ _ < k := by omega obtain ⟨x, -, hx⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt refine ⟨x, fun h => hx (h ▸ Finset.mem_insert_self _ _), fun w hw hfx => hx ?_⟩ exact Finset.mem_insert_of_mem (Finset.mem_image.2 ⟨w, by simpa using hw, hfx⟩)
In a bipartite partition V = A ⊔ B, neighbours alternate parts, and choice functions F1 and F3 provide free colours off c for α and β (rc32_route setup).
Because A and B are independent sets covering V, any neighbour of a vertex in A must lie in B, and vice versa. Applying rc32_free to α and β at each vertex gives choice functions F1 and F3 yielding colours distinct from c that avoid the neighbours' colours under α and β respectively.
uses
Or.resolve_left,Or.resolve_right,rc32_freetheorem rc32_route {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : G.maxDegree + 2 ≤ k) (A B : Finset V) (hcov : ∀ v, v ∈ A ∨ v ∈ B) (hdisj : ∀ v, v ∈ A → v ∉ B) (hA : ∀ v ∈ A, ∀ w ∈ A, ¬ G.Adj v w) (hB : ∀ v ∈ B, ∀ w ∈ B, ¬ G.Adj v w) (c : Fin k) (α β : G.Coloring (Fin k)) : ∃ w : (simple_graph_reconfiguration_graph G k).Walk α β, w.length + (A.filter (fun v => α v = c)).card + (A.filter (fun v => β v = c)).card ≤ 2 * A.card + B.card + (B.filter (fun v => α v = c)).card + (B.filter (fun v => β v = c)).card := by have otherA : ∀ v w, v ∈ A → G.Adj v w → w ∈ B := fun v w hv hvw => (hcov w).resolve_left (fun hw => hA v hv w hw hvw) have otherB : ∀ v w, v ∈ B → G.Adj v w → w ∈ A := fun v w hv hvw => (hcov w).resolve_right (fun hw => hB v hv w hw hvw) choose F1 hF1c hF1 using rc32_free G hk α c choose F3 hF3c hF3 using rc32_free G hk β c
Phase 1 reconfigures B to clear colour c, reaching a colouring γ1 via walk w1.
We apply rc32_assign to the independent set B, assigning each vertex v ∈ B with α(v) = c to its free colour F1(v) while keeping other vertices unchanged. Because neighbours of v lie in A and F1(v) is free under α, no neighbour shares this target colour. The walk recolours only vertices in B that currently have colour c.
uses
rc32_assign,if_pos,if_neg-- phase 1: move B off colour c obtain ⟨γ1, e1, w1, l1⟩ := rc32_assign G k (fun v => if α v = c then F1 v else α v) B hB α (by intro v hv w hvw by_cases h : α v = c · rw [if_pos h]; exact (hF1 v w hvw).symm · rw [if_neg h]; exact α.valid hvw)
Phase 2 reconfigures all vertices in A to colour c, reaching colouring γ2 via walk w2.
We apply rc32_assign to the independent set A with constant target colour c. This assignment is valid because after Phase 1, no vertex in B has colour c: those with α(w) = c were moved to F1(w) ≠ c, and all others already differed from c.
uses
rc32_assign,if_pos,if_neg,Ne.symm-- phase 2: colour A with c obtain ⟨γ2, e2, w2, l2⟩ := rc32_assign G k (fun _ => c) A hA γ1 (by intro v hv w hvw have hw := otherA v w hv hvw rw [e1 w, if_pos hw] by_cases h : α w = c · rw [if_pos h]; exact (hF1c w).symm · rw [if_neg h]; exact Ne.symm h) -- phase 3: B to β, parking the vertices whose β-colour is c
Phase 3 reconfigures B towards β, parking vertices with target β(v) = c at colour F3(v) ≠ c, reaching colouring γ3 via walk w3.
We apply rc32_assign to B with target β(v) if β(v) ≠ c and F3(v) if β(v) = c. All neighbours of B currently have colour c from Phase 2 on A; since both target options differ from c, no neighbour has the target colour.
uses
rc32_assign,if_pos,if_negobtain ⟨γ3, e3, w3, l3⟩ := rc32_assign G k (fun v => if β v ≠ c then β v else F3 v) B hB γ2 (by intro v hv w hvw have hw := otherB v w hv hvw rw [e2 w, if_pos hw] by_cases h : β v ≠ c · rw [if_pos h]; exact h · rw [if_neg h]; exact hF3c v)
Phase 4 reconfigures all of A to its target colouring β, reaching colouring γ4 via walk w4.
We apply rc32_assign to A with target β. In colouring γ3, no vertex in B has colour c because those needing c are parked at F3(w) ≠ c. For target colours different from c, properness of β ensures no neighbour shares the colour; for target colour c, no neighbour in B has colour c.
uses
rc32_assign,if_pos,if_neg-- phase 4: A to β obtain ⟨γ4, e4, w4, l4⟩ := rc32_assign G k (fun v => β v) A hA γ3 (by intro v hv w hvw have hw := otherA v w hv hvw rw [e3 w, if_pos hw] by_cases h : β w ≠ c · rw [if_pos h]; exact β.valid hvw · rw [if_neg h]; exact hF3 w v hvw.symm)
Phase 5 reconfigures the parked vertices of B to their target colour c, reaching colouring γ5 via walk w5.
We apply rc32_assign to B with target β. Since A has already reached its final colouring β and β is a proper colouring, no neighbour of any v ∈ B in A shares colour β(v), allowing all remaining vertices of B to take their target colour.
uses
rc32_assign,if_pos-- phase 5: B to β obtain ⟨γ5, e5, w5, l5⟩ := rc32_assign G k (fun v => β v) B hB γ4 (by intro v hv w hvw have hw := otherB v w hv hvw rw [e4 w, if_pos hw] exact β.valid hvw)
The final colouring γ5 equals β, and concatenating the five walks yields a reconfiguration walk from α to β.
Every vertex in B was set to β in Phase 5, and every vertex in A was set to β in Phase 4 and left untouched in Phase 5, so γ5 = β. Concatenating w1 through w5 with SimpleGraph.Walk.append and casting along γ5 = β gives a walk from α to β of length equal to the sum of the five phase lengths.
uses
if_pos,if_neg,Or.resolve_right,SimpleGraph.Walk.append,SimpleGraph.Walk.copy,SimpleGraph.Walk.length_copy,SimpleGraph.Walk.length_appendhave h5 : γ5 = β := by ext v rw [e5 v] by_cases hv : v ∈ B · rw [if_pos hv] · rw [if_neg hv, e4 v, if_pos ((hcov v).resolve_right hv)] refine ⟨((((w1.append w2).append w3).append w4).append w5).copy rfl h5, ?_⟩ simp only [SimpleGraph.Walk.length_copy, SimpleGraph.Walk.length_append]
The total length of the walk satisfies w.length + |{v ∈ A : α(v) = c}| + |{v ∈ A : β(v) = c}| ≤ 2|A| + |B| + |{v ∈ B : α(v) = c}| + |{v ∈ B : β(v) = c}|. automation
By rc32_assign, Phase 1 takes at most |{v ∈ B : α(v) = c}| steps; Phase 2 takes at most |{v ∈ A : α(v) ≠ c}| = |A| - |{v ∈ A : α(v) = c}| steps; Phase 3 takes at most |B| steps; Phase 4 takes at most |{v ∈ A : β(v) ≠ c}| = |A| - |{v ∈ A : β(v) = c}| steps; and Phase 5 takes at most |{v ∈ B : β(v) = c}| steps. The linear arithmetic solver omega combines these five bounds into the stated inequality.
uses
Finset.card_le_card,Finset.mem_filter,if_neg,Finset.filter_congr,add_comm,Finset.card_filter_add_card_filter_not,Finset.filter_subset,if_pos-- cost bounds have c1 : (B.filter (fun v => α v ≠ (if α v = c then F1 v else α v))).card ≤ (B.filter (fun v => α v = c)).card := by apply Finset.card_le_card intro v simp only [Finset.mem_filter] rintro ⟨hv, h⟩ refine ⟨hv, ?_⟩ by_contra hc exact h (by rw [if_neg hc]) have c2 : (A.filter (fun v => γ1 v ≠ c)).card + (A.filter (fun v => α v = c)).card = A.card := by have : A.filter (fun v => γ1 v ≠ c) = A.filter (fun v => ¬ α v = c) := by apply Finset.filter_congr intro v hv rw [e1 v, if_neg (hdisj v hv)] rw [this, add_comm] exact Finset.card_filter_add_card_filter_not _ have c3 : (B.filter (fun v => γ2 v ≠ (if β v ≠ c then β v else F3 v))).card ≤ B.card := Finset.card_le_card (Finset.filter_subset _ _) have c4 : (A.filter (fun v => γ3 v ≠ β v)).card + (A.filter (fun v => β v = c)).card = A.card := by have : A.filter (fun v => γ3 v ≠ β v) = A.filter (fun v => ¬ β v = c) := by apply Finset.filter_congr intro v hv rw [e3 v, if_neg (hdisj v hv), e2 v, if_pos hv] exact ⟨fun h h' => h h'.symm, fun h h' => h h'.symm⟩ rw [this, add_comm] exact Finset.card_filter_add_card_filter_not _ have hdisj' : ∀ v, v ∈ B → v ∉ A := fun v hv hvA => hdisj v hvA hv have c5 : (B.filter (fun v => γ4 v ≠ β v)).card ≤ (B.filter (fun v => β v = c)).card := by apply Finset.card_le_card intro v simp only [Finset.mem_filter] rintro ⟨hv, h⟩ refine ⟨hv, ?_⟩ rw [e4 v, if_neg (hdisj' v hv), e3 v, if_pos hv] at h by_contra hc exact h (by rw [if_pos hc]) omega
In a bipartite graph, the bipartition 2-colouring χ decomposes V into two disjoint independent sets A and B with |A| + |B| = |V|.
From hG : G.IsBipartite, we obtain a proper 2-colouring χ : V → Fin 2. Defining A = {v : χ(v) = 0} and B = {v : χ(v) ≠ 0} partitions V into two disjoint sets. Since χ assigns distinct colours to adjacent vertices, both A and B are independent sets, and their sizes sum to the total number of vertices |V|.
uses
Or.inl,Or.inr,Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_filter_add_card_filter_not,Finset.card_univ/-- Any two proper k-colourings of a bipartite graph are joined in the reconfiguration graph by a walk of length at most ⌊3n/2⌋ when k ≥ Δ + 2. -/ theorem simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) {k : ℕ} (hk : G.maxDegree + 2 ≤ k) (α β : G.Coloring (Fin k)) : ∃ w : (simple_graph_reconfiguration_graph G k).Walk α β, w.length ≤ 3 * Fintype.card V / 2 := by obtain ⟨χ⟩ := hG have key : ∀ a b : Fin 2, a ≠ b → (a = 0 ↔ ¬ b = 0) := by decide set A := Finset.univ.filter (fun v => χ v = 0) with hAdef set B := Finset.univ.filter (fun v => ¬ χ v = 0) with hBdef have hcov : ∀ v, v ∈ A ∨ v ∈ B := by intro v by_cases h : χ v = 0 · exact Or.inl (by simp [hAdef, h]) · exact Or.inr (by simp [hBdef, h]) have hdisj : ∀ v, v ∈ A → v ∉ B := by intro v hv hv' simp only [hAdef, hBdef, Finset.mem_filter, Finset.mem_univ, true_and] at hv hv' exact hv' hv have hA : ∀ v ∈ A, ∀ w ∈ A, ¬ G.Adj v w := by intro v hv w hw hvw simp only [hAdef, Finset.mem_filter, Finset.mem_univ, true_and] at hv hw exact (key _ _ (χ.valid hvw)).1 hv hw have hB : ∀ v ∈ B, ∀ w ∈ B, ¬ G.Adj v w := by intro v hv w hw hvw simp only [hBdef, Finset.mem_filter, Finset.mem_univ, true_and] at hv hw exact hw ((key _ _ (χ.valid hvw.symm)).2 hv) have hcard : A.card + B.card = Fintype.card V := by rw [hAdef, hBdef, Finset.card_filter_add_card_filter_not, Finset.card_univ] have hk2 : 0 < k := by omega
Applying rc32_route to both (A, B) and (B, A) yields two walks whose lengths sum to at most 3|V|, so the shorter walk has length at most 3|V|/2. automation
Applying rc32_route with colour 0 to (A, B) yields a walk w1, and applying it to (B, A) yields a walk w2. In the sum of their cost bounds, the terms counting vertices coloured 0 in A and B appear symmetrically on both sides of the inequality and cancel out completely, leaving w1.length + w2.length ≤ 3|A| + 3|B| = 3|V|. The decision procedure omega closes the goal by choosing whichever walk is shorter, which necessarily has length at most 3 * Fintype.card V / 2.
uses
rc32_routeobtain ⟨w1, h1⟩ := rc32_route G hk A B hcov hdisj hA hB ⟨0, hk2⟩ α β obtain ⟨w2, h2⟩ := rc32_route G hk B A (fun v => (hcov v).symm) (fun v hv hvA => hdisj v hvA hv) hB hA ⟨0, hk2⟩ α β by_cases hle : w1.length ≤ w2.length · exact ⟨w1, by omega⟩ · exact ⟨w2, by omega⟩
Finset.induction_on- A property holds for all finite sets if it holds for the empty set and is preserved under inserting a new element.
SimpleGraph.Walk.nil- The empty walk of length 0 from a vertex to itself.
Finset.mem_insert_of_mem- If an element belongs to a finite set, it also belongs to the set obtained by inserting another element.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.filter_subset_filter- Filtering preserves subset inclusion between finite sets.
Finset.subset_insert- Any finite set is a subset of the set obtained by inserting an element into it.
Finset.mem_insert_self- An inserted element belongs to the resulting set.
if_neg- An if-then-else expression evaluates to the else branch when the condition is false.
SimpleGraph.Coloring.mk- Constructs a proper graph colouring from a vertex-colour map and a proof that adjacent vertices receive distinct colours.
Function.update_self- Evaluating a function updated at point a with value v at argument a yields v.
Function.update_of_ne- Evaluating a function updated at point a' at a different point a ≠ a' yields the original value.
SimpleGraph.Walk.length_concat- Appending an edge to a walk increases its length by 1.
Finset.filter_insert- Filtering a set after inserting an element includes the inserted element if and only if it satisfies the predicate.
if_pos- An if-then-else expression evaluates to the then branch when the condition is true.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Nat.add_le_add_right- Adding the same natural number to both sides of an inequality preserves the inequality.
Finset.card_image_le- The image of a finite set under any function has cardinality at most that of the original set.
Finset.exists_mem_notMem_of_card_lt_card- If a finite set s has strictly smaller cardinality than t, there exists an element of t not in s.
Or.resolve_left- Given a disjunction a ∨ b and the negation ¬a, one concludes b.
Or.resolve_right- Given a disjunction a ∨ b and the negation ¬b, one concludes a.
rc32_free- When k ≥ Δ(G) + 2, for any vertex v and colour c, there is a colour x ≠ c not used by any neighbour of v under f.
rc32_assign- An independent set s can be recoloured to target colours g(v) by a reconfiguration walk of length at most the number of vertices where the current colouring differs from g, provided no neighbour shares target colour g(v).
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
SimpleGraph.Walk.append- Concatenates a walk from u to v and a walk from v to w into a walk from u to w.
SimpleGraph.Walk.copy- Replaces the endpoints of a walk with propositionally equal vertices without changing the walk.
SimpleGraph.Walk.length_copy- Casting the endpoints of a walk along an equality preserves its length.
SimpleGraph.Walk.length_append- The length of the concatenation of two walks is the sum of their lengths.
Finset.filter_congr- If two predicates are equivalent on a set, filtering by either predicate produces the same subset.
add_comm- Addition of natural numbers is commutative: a + b = b + a.
Finset.card_filter_add_card_filter_not- For any predicate on a finite set, the number of elements satisfying it plus the number of elements not satisfying it equals the total size.
Finset.filter_subset- Filtering a finite set by any predicate yields a subset of the original set.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies p.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- Conjunction with True is equivalent to the proposition itself: (True ∧ p) = p.
Or.inl- Introduces a disjunction from a proof of its left disjunct.
Or.inr- Introduces a disjunction from a proof of its right disjunct.
rc32_route- In a bipartite graph with partition V = A ⊔ B and colour c, any two colourings α, β are joined by a walk whose length plus c-counts on A is bounded by 2|A| + |B| plus c-counts on B.
- The cost bound in rc32_route (line 189) is verified by the omega linear arithmetic tactic, which combines five bounds on the lengths of the reconfiguration phases.
- The final bound min(w1.length, w2.length) ≤ 3 * |V| / 2 (lines 228–229) is closed by omega from the fact that w1.length + w2.length ≤ 3 * |V|.
- SimpleGraph.Walk.copy is used at line 148 to adjust the endpoints of the concatenated walk to match α and β definitionally after proving γ5 = β.
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.
theorem rc32_assign {V : Type*} [DecidableEq V] (G : SimpleGraph V) (k : ℕ) (g : V → Fin k) (s : Finset V) (hs : ∀ v ∈ s, ∀ w ∈ s, ¬ G.Adj v w) : ∀ γ : G.Coloring (Fin k), (∀ v ∈ s, ∀ w, G.Adj v w → g v ≠ γ w) → ∃ γ' : G.Coloring (Fin k), (∀ v, γ' v = if v ∈ s then g v else γ v) ∧ ∃ w : (simple_graph_reconfiguration_graph G k).Walk γ γ', w.length ≤ (s.filter (fun v => γ v ≠ g v)).card := by induction s using Finset.induction_on with | empty => intro γ _ exact ⟨γ, fun v => by simp, SimpleGraph.Walk.nil, by simp⟩ | @insert a s ha ih => intro γ hval have hs' : ∀ v ∈ s, ∀ w ∈ s, ¬ G.Adj v w := fun v hv w hw => hs v (Finset.mem_insert_of_mem hv) w (Finset.mem_insert_of_mem hw) obtain ⟨γ1, h1, w1, hw1⟩ := ih hs' γ (fun v hv w hvw => hval v (Finset.mem_insert_of_mem hv) w hvw) have hcard : (s.filter (fun v => γ v ≠ g v)).card ≤ ((insert a s).filter (fun v => γ v ≠ g v)).card := Finset.card_le_card (Finset.filter_subset_filter _ (Finset.subset_insert _ _)) by_cases hga : γ a = g a · refine ⟨γ1, fun v => ?_, w1, hw1.trans hcard⟩ rw [h1 v] by_cases hv : v = a · subst hv simp [ha, hga] · simp [hv] · have hnbr : ∀ w, G.Adj a w → g a ≠ γ1 w := by intro w haw have hw : w ∉ s := fun hw => hs a (Finset.mem_insert_self _ _) w (Finset.mem_insert_of_mem hw) haw rw [h1 w, if_neg hw] exact hval a (Finset.mem_insert_self _ _) w haw let γ2 : G.Coloring (Fin k) := SimpleGraph.Coloring.mk (Function.update γ1 a (g a)) (by intro x y hxy by_cases hx : x = a · subst hx have hy : y ≠ x := fun h => by subst h; exact G.irrefl hxy rw [Function.update_self, Function.update_of_ne hy] exact hnbr y hxy · by_cases hy : y = a · subst hy rw [Function.update_self, Function.update_of_ne hx] exact (hnbr x hxy.symm).symm · rw [Function.update_of_ne hx, Function.update_of_ne hy] exact γ1.valid hxy) have hγ2 : ∀ v, γ2 v = Function.update γ1 a (g a) v := fun v => rfl have hγ1a : γ1 a = γ a := by rw [h1 a, if_neg ha] have hadj : (simple_graph_reconfiguration_graph G k).Adj γ1 γ2 := by refine ⟨a, ?_, ?_⟩ · show γ1 a ≠ γ2 a rw [hγ2, Function.update_self, hγ1a] exact hga · intro u hu change γ1 u ≠ γ2 u at hu by_contra hua exact hu (by rw [hγ2, Function.update_of_ne hua]) refine ⟨γ2, fun v => ?_, w1.concat hadj, ?_⟩ · rw [hγ2] by_cases hv : v = a · subst hv simp · rw [Function.update_of_ne hv, h1 v] simp [hv] · rw [SimpleGraph.Walk.length_concat, Finset.filter_insert, if_pos hga, Finset.card_insert_of_notMem (by simp [ha])] omegatheorem rc32_free {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : G.maxDegree + 2 ≤ k) (f : V → Fin k) (c : Fin k) (v : V) : ∃ x : Fin k, x ≠ c ∧ ∀ w, G.Adj v w → f w ≠ x := by have hlt : (insert c ((G.neighborFinset v).image f)).card < (Finset.univ : Finset (Fin k)).card := by rw [Finset.card_univ, Fintype.card_fin] calc (insert c ((G.neighborFinset v).image f)).card ≤ ((G.neighborFinset v).image f).card + 1 := Finset.card_insert_le _ _ _ ≤ (G.neighborFinset v).card + 1 := Nat.add_le_add_right Finset.card_image_le _ _ ≤ G.maxDegree + 1 := by rw [G.card_neighborFinset_eq_degree] exact Nat.add_le_add_right (G.degree_le_maxDegree v) _ _ < k := by omega obtain ⟨x, -, hx⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt refine ⟨x, fun h => hx (h ▸ Finset.mem_insert_self _ _), fun w hw hfx => hx ?_⟩ exact Finset.mem_insert_of_mem (Finset.mem_image.2 ⟨w, by simpa using hw, hfx⟩)theorem rc32_route {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : G.maxDegree + 2 ≤ k) (A B : Finset V) (hcov : ∀ v, v ∈ A ∨ v ∈ B) (hdisj : ∀ v, v ∈ A → v ∉ B) (hA : ∀ v ∈ A, ∀ w ∈ A, ¬ G.Adj v w) (hB : ∀ v ∈ B, ∀ w ∈ B, ¬ G.Adj v w) (c : Fin k) (α β : G.Coloring (Fin k)) : ∃ w : (simple_graph_reconfiguration_graph G k).Walk α β, w.length + (A.filter (fun v => α v = c)).card + (A.filter (fun v => β v = c)).card ≤ 2 * A.card + B.card + (B.filter (fun v => α v = c)).card + (B.filter (fun v => β v = c)).card := by have otherA : ∀ v w, v ∈ A → G.Adj v w → w ∈ B := fun v w hv hvw => (hcov w).resolve_left (fun hw => hA v hv w hw hvw) have otherB : ∀ v w, v ∈ B → G.Adj v w → w ∈ A := fun v w hv hvw => (hcov w).resolve_right (fun hw => hB v hv w hw hvw) choose F1 hF1c hF1 using rc32_free G hk α c choose F3 hF3c hF3 using rc32_free G hk β c -- phase 1: move B off colour c obtain ⟨γ1, e1, w1, l1⟩ := rc32_assign G k (fun v => if α v = c then F1 v else α v) B hB α (by intro v hv w hvw by_cases h : α v = c · rw [if_pos h]; exact (hF1 v w hvw).symm · rw [if_neg h]; exact α.valid hvw) -- phase 2: colour A with c obtain ⟨γ2, e2, w2, l2⟩ := rc32_assign G k (fun _ => c) A hA γ1 (by intro v hv w hvw have hw := otherA v w hv hvw rw [e1 w, if_pos hw] by_cases h : α w = c · rw [if_pos h]; exact (hF1c w).symm · rw [if_neg h]; exact Ne.symm h) -- phase 3: B to β, parking the vertices whose β-colour is c obtain ⟨γ3, e3, w3, l3⟩ := rc32_assign G k (fun v => if β v ≠ c then β v else F3 v) B hB γ2 (by intro v hv w hvw have hw := otherB v w hv hvw rw [e2 w, if_pos hw] by_cases h : β v ≠ c · rw [if_pos h]; exact h · rw [if_neg h]; exact hF3c v) -- phase 4: A to β obtain ⟨γ4, e4, w4, l4⟩ := rc32_assign G k (fun v => β v) A hA γ3 (by intro v hv w hvw have hw := otherA v w hv hvw rw [e3 w, if_pos hw] by_cases h : β w ≠ c · rw [if_pos h]; exact β.valid hvw · rw [if_neg h]; exact hF3 w v hvw.symm) -- phase 5: B to β obtain ⟨γ5, e5, w5, l5⟩ := rc32_assign G k (fun v => β v) B hB γ4 (by intro v hv w hvw have hw := otherB v w hv hvw rw [e4 w, if_pos hw] exact β.valid hvw) have h5 : γ5 = β := by ext v rw [e5 v] by_cases hv : v ∈ B · rw [if_pos hv] · rw [if_neg hv, e4 v, if_pos ((hcov v).resolve_right hv)] refine ⟨((((w1.append w2).append w3).append w4).append w5).copy rfl h5, ?_⟩ simp only [SimpleGraph.Walk.length_copy, SimpleGraph.Walk.length_append] -- cost bounds have c1 : (B.filter (fun v => α v ≠ (if α v = c then F1 v else α v))).card ≤ (B.filter (fun v => α v = c)).card := by apply Finset.card_le_card intro v simp only [Finset.mem_filter] rintro ⟨hv, h⟩ refine ⟨hv, ?_⟩ by_contra hc exact h (by rw [if_neg hc]) have c2 : (A.filter (fun v => γ1 v ≠ c)).card + (A.filter (fun v => α v = c)).card = A.card := by have : A.filter (fun v => γ1 v ≠ c) = A.filter (fun v => ¬ α v = c) := by apply Finset.filter_congr intro v hv rw [e1 v, if_neg (hdisj v hv)] rw [this, add_comm] exact Finset.card_filter_add_card_filter_not _ have c3 : (B.filter (fun v => γ2 v ≠ (if β v ≠ c then β v else F3 v))).card ≤ B.card := Finset.card_le_card (Finset.filter_subset _ _) have c4 : (A.filter (fun v => γ3 v ≠ β v)).card + (A.filter (fun v => β v = c)).card = A.card := by have : A.filter (fun v => γ3 v ≠ β v) = A.filter (fun v => ¬ β v = c) := by apply Finset.filter_congr intro v hv rw [e3 v, if_neg (hdisj v hv), e2 v, if_pos hv] exact ⟨fun h h' => h h'.symm, fun h h' => h h'.symm⟩ rw [this, add_comm] exact Finset.card_filter_add_card_filter_not _ have hdisj' : ∀ v, v ∈ B → v ∉ A := fun v hv hvA => hdisj v hvA hv have c5 : (B.filter (fun v => γ4 v ≠ β v)).card ≤ (B.filter (fun v => β v = c)).card := by apply Finset.card_le_card intro v simp only [Finset.mem_filter] rintro ⟨hv, h⟩ refine ⟨hv, ?_⟩ rw [e4 v, if_neg (hdisj' v hv), e3 v, if_pos hv] at h by_contra hc exact h (by rw [if_pos hc]) omega/-- Any two proper k-colourings of a bipartite graph are joined in the reconfiguration graph by a walk of length at most ⌊3n/2⌋ when k ≥ Δ + 2. -/theorem simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) {k : ℕ} (hk : G.maxDegree + 2 ≤ k) (α β : G.Coloring (Fin k)) : ∃ w : (simple_graph_reconfiguration_graph G k).Walk α β, w.length ≤ 3 * Fintype.card V / 2 := by obtain ⟨χ⟩ := hG have key : ∀ a b : Fin 2, a ≠ b → (a = 0 ↔ ¬ b = 0) := by decide set A := Finset.univ.filter (fun v => χ v = 0) with hAdef set B := Finset.univ.filter (fun v => ¬ χ v = 0) with hBdef have hcov : ∀ v, v ∈ A ∨ v ∈ B := by intro v by_cases h : χ v = 0 · exact Or.inl (by simp [hAdef, h]) · exact Or.inr (by simp [hBdef, h]) have hdisj : ∀ v, v ∈ A → v ∉ B := by intro v hv hv' simp only [hAdef, hBdef, Finset.mem_filter, Finset.mem_univ, true_and] at hv hv' exact hv' hv have hA : ∀ v ∈ A, ∀ w ∈ A, ¬ G.Adj v w := by intro v hv w hw hvw simp only [hAdef, Finset.mem_filter, Finset.mem_univ, true_and] at hv hw exact (key _ _ (χ.valid hvw)).1 hv hw have hB : ∀ v ∈ B, ∀ w ∈ B, ¬ G.Adj v w := by intro v hv w hw hvw simp only [hBdef, Finset.mem_filter, Finset.mem_univ, true_and] at hv hw exact hw ((key _ _ (χ.valid hvw.symm)).2 hv) have hcard : A.card + B.card = Fintype.card V := by rw [hAdef, hBdef, Finset.card_filter_add_card_filter_not, Finset.card_univ] have hk2 : 0 < k := by omega obtain ⟨w1, h1⟩ := rc32_route G hk A B hcov hdisj hA hB ⟨0, hk2⟩ α β obtain ⟨w2, h2⟩ := rc32_route G hk B A (fun v => (hcov v).symm) (fun v hv hvA => hdisj v hvA hv) hB hA ⟨0, hk2⟩ α β by_cases hle : w1.length ≤ w2.length · exact ⟨w1, by omega⟩ · exact ⟨w2, by omega⟩