op_1611_min_max_degree_le_eight
The natural number 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
Statement
theorem op_1611_min_max_degree_le_eight :
simple_graph_reconfiguration_diam_gt_matching 8- Formalizes
- arXiv:2611.17022 Theorem 4
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- simple_graph_reconfiguration_diam_gt_matchingThe predicate on a natural number Δ asserting that there exists a finite simple graph G on a finite type V with decidable equality and…
- graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
- 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…
- graph_matching_num_le_vertex_cover_numIn any simple graph G, the matching number is at most the vertex cover number.
- Arena.Reachable.transReachability is transitive.
- Used by 1
- op_1611_target_of_eight_and_threeIf 8 satisfies the witness predicate and no Δ ≤ 3 does, then there is a unique Δ with 4 ≤ Δ ≤ 8 that is least in the set of witnesses.
Read back from the Lean
There exists a finite type $V$ with decidable equality, and a simple graph $G$ on $V$ with decidable adjacency, such that:
1. The maximum degree of $G$ is equal to $8$ (G.maxDegree = 8), and
2. The number of vertices $|V|$ plus the matching number of $G$ (both regarded in $\mathbb{N}_\infty$) is strictly less than the diameter of the reconfiguration graph of proper $10$-colorings of $G$ (that is, the graph whose vertices are proper colorings of $G$ with colors in $\mathrm{Fin}(10)$, where two colorings are adjacent if and only if they differ at exactly one vertex).
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 theorem proves that Δ = 8 satisfies the reconfiguration diameter-matching property by constructing a bipartite graph G₅ on 25 vertices, the 1-subdivision of the doubled complete graph 2K₅. The graph has maximum degree 8, matching number at most 5 (witnessed by the 5 diagonal vertices forming a vertex cover), and a connected 10-reconfiguration graph. Two specific 10-colorings α₅ and β₅ disagree everywhere, and combinatorial case analysis and counting show that any recoloring walk between them requires at least 31 single-vertex color modifications. Consequently, the diameter of the 10-reconfiguration graph is at least 31, strictly exceeding |V(G₅)| + ν(G₅) = 25 + 5 = 30.
G₅ is a well-defined, loopless, symmetric graph on Fin 5 × Fin 5.
The graph G₅ is the 1-subdivision of the doubled complete graph 2K₅. Its vertices are divided into 5 diagonal vertices (i, i) and 20 off-diagonal vertices (i, j) with i ≠ j. Symmetry of the adjacency relation is immediate by propositional logic, and looplessness holds because no vertex can satisfy both p.1 = p.2 and p.1 ≠ p.2.
def G5 : SimpleGraph (Fin 5 × Fin 5) where Adj p q := (p.1 = p.2 ∧ q.1 ≠ q.2 ∧ (q.1 = p.1 ∨ q.2 = p.1)) ∨ (q.1 = q.2 ∧ p.1 ≠ p.2 ∧ (p.1 = q.1 ∨ p.2 = q.1)) symm := ⟨fun p q h => by tauto⟩ loopless := ⟨fun p h => by rcases h with ⟨h1, h2, _⟩ | ⟨h1, h2, _⟩ <;> exact h2 h1⟩
The maximum degree of G₅ is 8. automation
Exhaustive kernel evaluation verifies that every vertex in G₅ has degree at most 8 and that vertex (0, 0) has degree exactly 8. Hence the maximum degree Δ(G₅) equals 8.
theorem G5_degree_le : ∀ p, G5.degree p ≤ 8 := by decide +kernel theorem G5_degree_x : G5.degree (0, 0) = 8 := by decide +kernel theorem G5_maxDegree : G5.maxDegree = 8 := le_antisymm (G5.maxDegree_le_of_forall_degree_le 8 G5_degree_le) (G5_degree_x ▸ G5.degree_le_maxDegree _)
The matching number of G₅ is at most 5.
By weak duality (graph_matching_num_le_vertex_cover_num), the matching number of any graph is at most its vertex cover number. The 5 diagonal vertices { (i, i) : i ∈ Fin 5 } form a vertex cover since every edge in G₅ has at least one endpoint with equal coordinates. Consequently, the vertex cover number and matching number are both at most 5.
uses
graph_matching_num_le_vertex_cover_num,Set.encard_coe_eq_coe_finsetCardtheorem G5_matching : graph_matching_num G5 ≤ 5 := by refine (graph_matching_num_le_vertex_cover_num G5).trans ?_ have hc : G5.IsVertexCover {p | p.1 = p.2} := by intro p q h change _ ∨ _ at h rcases h with h | h · exact Or.inl h.1 · exact Or.inr h.1 refine hc.vertexCoverNum_le.trans ?_ have : ({p | p.1 = p.2} : Set (Fin 5 × Fin 5)) = ((Finset.univ.filter fun p : Fin 5 × Fin 5 => p.1 = p.2 : Finset _) : Set _) := by ext p; simp rw [this, Set.encard_coe_eq_coe_finsetCard] have h5 : (Finset.univ.filter fun p : Fin 5 × Fin 5 => p.1 = p.2).card = 5 := by decide rw [h5]; rfl
α₅ is a valid 10-coloring of G₅.
The coloring α₅ assigns color i to diagonal vertex (i, i) and 5 + i to off-diagonal vertex (i, j) for i ≠ j. Adjacent vertices consist of one diagonal and one off-diagonal vertex; case splitting and linear arithmetic confirm that their colors are always distinct in Fin 10.
/-- Colouring α: `xᵢ ↦ aᵢ = i`, `y_ij ↦ bᵢ = 5 + i`. -/ def α5 : G5.Coloring (Fin 10) := SimpleGraph.Coloring.mk (fun p => ⟨if p.1 = p.2 then p.1.val else 5 + p.1.val, by split <;> omega⟩) (by intro p q h heq have hv := congrArg Fin.val heq dsimp only at hv change _ ∨ _ at h rcases h with ⟨h1, h2, h3⟩ | ⟨h1, h2, h3⟩ <;> simp only [Fin.ext_iff, ne_eq] at h1 h2 h3 <;> split_ifs at hv <;> simp only [Fin.ext_iff] at * <;> omega)
β₅ is a valid 10-coloring of G₅.
The coloring β₅ assigns color 5 + i to diagonal vertex (i, i) and j to off-diagonal vertex (i, j) for i ≠ j. As with α₅, case analysis and arithmetic confirm that adjacent vertices never share the same color.
/-- Colouring β: `xᵢ ↦ bᵢ = 5 + i`, `y_ij ↦ aⱼ = j`. -/ def β5 : G5.Coloring (Fin 10) := SimpleGraph.Coloring.mk (fun p => ⟨if p.1 = p.2 then 5 + p.1.val else p.2.val, by split <;> omega⟩) (by intro p q h heq have hv := congrArg Fin.val heq dsimp only at hv change _ ∨ _ at h rcases h with ⟨h1, h2, h3⟩ | ⟨h1, h2, h3⟩ <;> simp only [Fin.ext_iff, ne_eq] at h1 h2 h3 <;> split_ifs at hv <;> simp only [Fin.ext_iff] at * <;> omega)
α₅ and β₅ disagree at every vertex of G₅. automation
Kernel evaluation checks all 25 vertices to confirm that α₅(p) ≠ β₅(p) for every vertex p.
theorem α5_ne_β5 : ∀ p, α5 p ≠ β5 p := by decide +kernel
Reconfiguration steps for distinct vertices are disjoint, and their total count is at most the walk length.
Because each step of a reconfiguration walk modifies at most one vertex, the sets steps(w, v) of time indices where vertex v changes are pairwise disjoint across vertices (steps_unique). Taking the union over all vertices shows that the sum of the cardinalities of these sets is bounded by the length of the walk (sum_steps_le).
uses
steps_unique,Finset.card_biUnion,Finset.card_le_cardtheorem steps_unique {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {u v : V} {s : ℕ} (hu : s ∈ steps w u) (hv : s ∈ steps w v) : u = v := by simp only [steps, Finset.mem_filter, Finset.mem_range] at hu hv obtain ⟨x, _, hx⟩ := w.adj_getVert_succ hu.1 exact (hx u hu.2).trans (hx v hv.2).symm theorem sum_steps_le {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) : ∑ v, (steps w v).card ≤ w.length := by rw [← Finset.card_biUnion] · calc _ ≤ (Finset.range w.length).card := by apply Finset.card_le_card intro s hs simp only [Finset.mem_biUnion] at hs obtain ⟨v, _, hv⟩ := hs simp only [steps, Finset.mem_filter] at hv exact hv.1 _ = _ := Finset.card_range _ · intro u _ v _ huv exact Finset.disjoint_left.mpr fun _ hu hv => huv (steps_unique w hu hv)
Vertices remain constant outside change steps, and every vertex differing between start and end changes at least once.
Induction on time shows that a vertex v retains its color across any interval containing no steps in steps(w, v) (getVert_const). Since α₅(v) ≠ β₅(v), each vertex v must change color at least once, meaning |steps(w, v)| ≥ 1.
uses
Nat.le_induction,getVert_consttheorem getVert_const {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) (v : V) (k : ℕ) : ∀ k', k ≤ k' → (∀ s, k ≤ s → s < k' → s ∉ steps w v) → w.getVert k v = w.getVert k' v := by intro k' hk induction k', hk using Nat.le_induction with | base => intro _; rfl | succ n hn ih => intro h rw [ih (fun s h1 h2 => h s h1 (by omega))] by_contra hne by_cases hL : n < w.length · exact h n hn (by omega) (by simp [steps, hL, hne]) · apply hne rw [w.getVert_of_length_le (by omega), w.getVert_of_length_le (by omega)] theorem steps_nonempty {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {v : V} (h : a v ≠ b v) : 1 ≤ (steps w v).card := by rw [Nat.one_le_iff_ne_zero, Ne, Finset.card_eq_zero] intro h0 apply h have := getVert_const w v 0 w.length (Nat.zero_le _) (by simp [h0]) simpa using this
Trajectories of vertices changing once or twice are completely characterized.
A vertex changing only once switches directly from its initial to its final color at step s (steps_one). A vertex changing twice visits an intermediate color m distinct from both its initial and final colors, transitioning as initial → m → final (steps_two).
uses
steps_one,steps_two,getVert_consttheorem steps_one {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {v : V} {s : ℕ} (h : steps w v = {s}) (k : ℕ) : w.getVert k v = if k ≤ s then a v else b v := by have hs : s < w.length := by have : s ∈ steps w v := by simp [h] simp only [steps, Finset.mem_filter, Finset.mem_range] at this; exact this.1 split_ifs with hk · have := getVert_const w v 0 k (Nat.zero_le _) (by intro t _ ht; simp [h]; omega) simpa using this.symm · by_cases hkL : k ≤ w.length · have := getVert_const w v k w.length hkL (by intro t ht _; simp [h]; omega) simpa using this · rw [w.getVert_of_length_le (by omega)] theorem steps_two {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {v : V} {s₁ s₂ : ℕ} (h : steps w v = {s₁, s₂}) (h12 : s₁ < s₂) : ∃ m, m ≠ a v ∧ m ≠ b v ∧ ∀ k, w.getVert k v = if k ≤ s₁ then a v else if k ≤ s₂ then m else b v := by have hm1 : s₁ ∈ steps w v := by simp [h] have hm2 : s₂ ∈ steps w v := by simp [h] simp only [steps, Finset.mem_filter, Finset.mem_range] at hm1 hm2 have e0 : ∀ k, k ≤ s₁ → w.getVert k v = a v := fun k hk => by have := getVert_const w v 0 k (Nat.zero_le _) (by intro t _ ht; simp [h]; omega) simpa using this.symm have e1 : ∀ k, s₁ < k → k ≤ s₂ → w.getVert k v = w.getVert (s₁ + 1) v := fun k hk1 hk2 => by have := getVert_const w v (s₁ + 1) k hk1 (by intro t ht1 ht2; simp [h]; omega) exact this.symm have e2 : ∀ k, s₂ < k → w.getVert k v = b v := fun k hk => by by_cases hkL : k ≤ w.length · have := getVert_const w v k w.length hkL (by intro t ht _; simp [h]; omega) simpa using this · rw [w.getVert_of_length_le (by omega)] refine ⟨w.getVert (s₁ + 1) v, ?_, ?_, ?_⟩ · rw [← e0 s₁ le_rfl]; exact fun hh => hm1.2 hh.symm · rw [← e2 (s₂ + 1) (by omega), ← e1 s₂ h12 le_rfl]; exact hm2.2 · intro k split_ifs with ha hb · exact e0 k ha · exact e1 k (by omega) hb · exact e2 k (by omega)
Distinct vertices cannot change at the same step.
If p ≠ q, any step index at which p changes must be distinct from any step index at which q changes, because each transition modifies a unique vertex.
uses
steps_uniquetheorem step_ne {p q : Fin 5 × Fin 5} (hpq : p ≠ q) {s t : ℕ} (hs : s ∈ steps w p) (ht : t ∈ steps w q) : s ≠ t := by rintro rfl; exact hpq (steps_unique w hs ht)
Claim 2: Four adjacent vertices (i, i), (j, j), (i, j), and (j, i) cannot all change color only once.
Suppose all four vertices change exactly once, at step indices s₁, s₂, t₁, t₂ respectively. Evaluating colors at transition times and testing all relative orderings of the step indices shows that at least one adjacent pair would have identical colors at some intermediate state, contradicting the validity of the colorings along the walk.
uses
step_ne,steps_one,prop_at,adj_x_y,adj_x_y'theorem claim2 {i j : Fin 5} (hij : i ≠ j) {s₁ s₂ t₁ t₂ : ℕ} (h1 : steps w (i, i) = {s₁}) (h2 : steps w (j, j) = {s₂}) (h3 : steps w (i, j) = {t₁}) (h4 : steps w (j, i) = {t₂}) : False := by have hji : j ≠ i := Ne.symm hij have hi : (i : ℕ) ≠ j := fun h => hij (Fin.ext h) have d1 : t₁ ≠ s₁ := step_ne w (p := (i, j)) (q := (i, i)) (by simp [hij, hji]) (by simp [h3]) (by simp [h1]) have d2 : t₁ ≠ s₂ := step_ne w (p := (i, j)) (q := (j, j)) (by simp [hij, hji]) (by simp [h3]) (by simp [h2]) have d3 : t₂ ≠ s₁ := step_ne w (p := (j, i)) (q := (i, i)) (by simp [hij, hji]) (by simp [h4]) (by simp [h1]) have d4 : t₂ ≠ s₂ := step_ne w (p := (j, i)) (q := (j, j)) (by simp [hij, hji]) (by simp [h4]) (by simp [h2]) have c1 := prop_at w (adj_x_y hij) t₁ have c2 := prop_at w (adj_x_y' hij) (t₁ + 1) have c3 := prop_at w (adj_x_y hji) t₂ have c4 := prop_at w (adj_x_y' hji) (t₂ + 1) rw [steps_one w h1, steps_one w h3] at c1 rw [steps_one w h2, steps_one w h3] at c2 rw [steps_one w h2, steps_one w h4] at c3 rw [steps_one w h1, steps_one w h4] at c4 simp only [apply_ite Fin.val, α5_val, β5_val, hij, hji, if_true, if_false] at c1 c2 c3 c4 split_ifs at c1 c2 c3 c4 <;> omega
Claim 1: If diagonal vertex (i, i) changes twice, some incident off-diagonal vertex changes at least twice.
When (i, i) changes twice, its intermediate color m identifies an index j ≠ i (either j = m if m < 5, or j = m - 5 if m ≥ 5). If both (i, j) and (j, i) changed only once, evaluating colors at transition steps forces a color collision between (i, i) and one of the two off-diagonal neighbors. Hence at least one of (i, j) or (j, i) must change at least twice.
uses
claim1_aux,steps_two,steps_onetheorem claim1_aux {i : Fin 5} {s₁ s₂ : ℕ} (h : steps w (i, i) = {s₁, s₂}) (h12 : s₁ < s₂) : ∃ j, j ≠ i ∧ (2 ≤ (steps w (i, j)).card ∨ 2 ≤ (steps w (j, i)).card) := by obtain ⟨m, hm1, hm2, hf⟩ := steps_two w h h12 have hm1' : m.val ≠ i.val := fun e => hm1 (Fin.ext (by simp [α5_val, e])) have hm2' : m.val ≠ 5 + i.val := fun e => hm2 (Fin.ext (by simp [β5_val, e])) have hs1 : s₁ ∈ steps w (i, i) := by simp [h] have hs2 : s₂ ∈ steps w (i, i) := by simp [h] by_cases hm : m.val < 5 · set j : Fin 5 := ⟨m.val, hm⟩ with hjdef have hij : i ≠ j := fun e => hm1' (by rw [e]) refine ⟨j, Ne.symm hij, Or.inl ?_⟩ by_contra hlt have hge := steps_nonempty w (α5_ne_β5 (i, j)) obtain ⟨t, ht⟩ := Finset.card_eq_one.mp (by omega : (steps w (i, j)).card = 1) have htm : t ∈ steps w (i, j) := by simp [ht] have d1 := step_ne w (p := (i, j)) (q := (i, i)) (by simp [hij, Ne.symm hij]) htm hs1 have d2 := step_ne w (p := (i, j)) (q := (i, i)) (by simp [hij, Ne.symm hij]) htm hs2 have c1 := prop_at w (adj_x_y hij) (s₁ + 1) have c2 := prop_at w (adj_x_y hij) (t + 1) have c3 := prop_at w (adj_x_y hij) (s₂ + 1) rw [hf, steps_one w ht] at c1 c2 c3 simp only [apply_ite Fin.val, α5_val, β5_val, hij, if_true, if_false, hjdef] at c1 c2 c3 split_ifs at c1 c2 c3 <;> omega · set j : Fin 5 := ⟨m.val - 5, by omega⟩ with hjdef have hji : j ≠ i := fun e => hm2' (by rw [← e]; simp [hjdef]; omega) refine ⟨j, hji, Or.inr ?_⟩ by_contra hlt have hge := steps_nonempty w (α5_ne_β5 (j, i)) obtain ⟨t, ht⟩ := Finset.card_eq_one.mp (by omega : (steps w (j, i)).card = 1) have htm : t ∈ steps w (j, i) := by simp [ht] have d1 := step_ne w (p := (j, i)) (q := (i, i)) (by simp [hji, Ne.symm hji]) htm hs1 have c1 := prop_at w (adj_x_y' hji) (s₁ + 1) have c2 := prop_at w (adj_x_y' hji) (t + 1) rw [hf, steps_one w ht] at c1 c2 simp only [apply_ite Fin.val, α5_val, β5_val, hji, if_true, if_false, hjdef] at c1 c2 split_ifs at c1 c2 <;> omega theorem claim1 {i : Fin 5} (h : (steps w (i, i)).card = 2) : ∃ j, j ≠ i ∧ (2 ≤ (steps w (i, j)).card ∨ 2 ≤ (steps w (j, i)).card) := by obtain ⟨x, y, hxy, he⟩ := Finset.card_eq_two.mp h rcases lt_or_gt_of_ne hxy with hlt | hlt · exact claim1_aux w he hlt · exact claim1_aux w (he.trans (Finset.pair_comm x y)) hlt end claims
Any vertex change count assignment satisfying Claims 1 and 2 sums to at least 31.
For each index i, count_key proves a local lower bound 10 + bonusF(f, i) ≤ ∑ j, (n(i, j) + n(j, i)), where the bonus term depends on whether n(i, i) equals 1, 2, or more. By exhaustive boolean verification, the bonus terms sum to at least 11 (bonus_sum). Summing over all 5 indices yields 50 + 11 = 61 ≤ 2 ∑ p, n(p), which implies ∑ p, n(p) ≥ 31.
uses
bonus_sum,count_key,counttheorem bonus_sum : ∀ f : Fin 5 → Bool, 11 ≤ ∑ i, bonusF f i := by decide theorem count_key (n : Fin 5 × Fin 5 → ℕ) (h1 : ∀ p, 1 ≤ n p) (hA : ∀ i j, i ≠ j → n (i, i) = 1 → n (j, j) = 1 → 2 ≤ n (i, j) ∨ 2 ≤ n (j, i)) (hB : ∀ i, n (i, i) = 2 → ∃ j, j ≠ i ∧ (2 ≤ n (i, j) ∨ 2 ≤ n (j, i))) (i : Fin 5) : 10 + bonusF (fun j => decide (n (j, j) = 1)) i ≤ ∑ j, (n (i, j) + n (j, i)) := by rw [← Finset.add_sum_erase _ _ (Finset.mem_univ i)] have hc : (Finset.univ.erase i).card = 4 := by simp have base : ∀ j ∈ Finset.univ.erase i, 2 ≤ n (i, j) + n (j, i) := fun j _ => by have := h1 (i, j); have := h1 (j, i); omega unfold bonusF by_cases hi1 : n (i, i) = 1 · simp only [hi1, decide_true, if_true] have : ∑ j ∈ Finset.univ.erase i, (2 + if n (j, j) = 1 then 1 else 0) ≤ ∑ j ∈ Finset.univ.erase i, (n (i, j) + n (j, i)) := by apply Finset.sum_le_sum intro j hj have hb := base j hj have := h1 (i, j); have := h1 (j, i) have hji : j ≠ i := Finset.ne_of_mem_erase hj split_ifs with hj1 · rcases hA i j (Ne.symm hji) hi1 hj1 with h | h <;> omega · omega rw [Finset.sum_add_distrib, Finset.sum_const, hc, Finset.sum_boole] at this simp only [smul_eq_mul, Nat.cast_id] at this have e : ((Finset.univ.erase i).filter (fun j => decide (n (j, j) = 1) = true)) = ((Finset.univ.erase i).filter (fun j => n (j, j) = 1)) := by ext j; simp rw [e]; omega · have hd : decide (n (i, i) = 1) = false := by simp [hi1] simp only [hd, if_false, Bool.false_eq_true] have hii := h1 (i, i) by_cases hi2 : n (i, i) = 2 · obtain ⟨j0, hj0, hj0'⟩ := hB i hi2 have : ∑ j ∈ Finset.univ.erase i, (2 + if j = j0 then 1 else 0) ≤ ∑ j ∈ Finset.univ.erase i, (n (i, j) + n (j, i)) := by apply Finset.sum_le_sum intro j hj have hb := base j hj have := h1 (i, j); have := h1 (j, i) split_ifs with hj1 · subst hj1; rcases hj0' with h | h <;> omega · omega rw [Finset.sum_add_distrib, Finset.sum_const, hc, Finset.sum_ite_eq' (Finset.univ.erase i) j0 (fun _ => 1)] at this simp only [Finset.mem_erase, ne_eq, hj0, not_false_eq_true, Finset.mem_univ, and_self, if_true, smul_eq_mul] at this omega · have : ∑ j ∈ Finset.univ.erase i, 2 ≤ ∑ j ∈ Finset.univ.erase i, (n (i, j) + n (j, i)) := Finset.sum_le_sum base rw [Finset.sum_const, hc, smul_eq_mul] at this omega theorem count (n : Fin 5 × Fin 5 → ℕ) (h1 : ∀ p, 1 ≤ n p) (hA : ∀ i j, i ≠ j → n (i, i) = 1 → n (j, j) = 1 → 2 ≤ n (i, j) ∨ 2 ≤ n (j, i)) (hB : ∀ i, n (i, i) = 2 → ∃ j, j ≠ i ∧ (2 ≤ n (i, j) ∨ 2 ≤ n (j, i))) : 31 ≤ ∑ p, n p := by have e1 : ∑ p, n p = ∑ i, ∑ j, n (i, j) := Fintype.sum_prod_type _ have e2 : ∑ i, ∑ j, n (j, i) = ∑ i, ∑ j, n (i, j) := Finset.sum_comm have hsum : ∑ i, (10 + bonusF (fun j => decide (n (j, j) = 1)) i) ≤ ∑ i, ∑ j, (n (i, j) + n (j, i)) := Finset.sum_le_sum fun i _ => count_key n h1 hA hB i simp only [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hsum have hb := bonus_sum (fun j => decide (n (j, j) = 1)) omega
Reconfiguration graphs of K-colorings are connected whenever K ≥ Δ(G) + 2.
Since K ≥ Δ + 2, every vertex u has an available color distinct from any target color b and distinct from all neighbor colors (exists_free_colour). Shifting conflicting neighbors away allows recoloring u to its target color (clear_nbrs). Proceeding vertex by vertex shows that any coloring can reach the target coloring β (reach_beta), establishing connectivity (recolour_connected).
uses
exists_free_colour,reach_update,clear_nbrs,reach_beta,recolour_connectedtheorem reach_update (c : G.Coloring (Fin K)) (u : V) (col : Fin K) (hv : ∀ x, G.Adj u x → c x ≠ col) : ∃ c' : G.Coloring (Fin K), (∀ x, c' x = Function.update c u col x) ∧ (simple_graph_reconfiguration_graph G K).Reachable c c' := by let c' : G.Coloring (Fin K) := SimpleGraph.Coloring.mk (Function.update c u col) (by intro a b hab by_cases ha : a = u · subst ha have hb : b ≠ a := (G.ne_of_adj hab).symm simp only [Function.update_self, Function.update_of_ne hb] exact (hv b hab).symm · by_cases hb : b = u · subst hb simp only [Function.update_self, Function.update_of_ne ha] exact hv a hab.symm · simp only [Function.update_of_ne ha, Function.update_of_ne hb] exact c.valid hab) refine ⟨c', fun x => rfl, ?_⟩ by_cases hc : c u = col · have : c = c' := by refine RelHom.ext fun x => ?_ show c x = Function.update c u col x by_cases hx : x = u · subst hx; simp [hc] · simp [Function.update_of_ne hx] rw [this] · apply SimpleGraph.Adj.reachable refine ⟨u, ?_, ?_⟩ · show c u ≠ Function.update c u col u simpa using hc · intro y hy by_contra hyu apply hy show c y = Function.update c u col y simp [Function.update_of_ne hyu] theorem exists_free_colour (hk : G.maxDegree + 2 ≤ K) (c : G.Coloring (Fin K)) (u : V) (b : Fin K) : ∃ col : Fin K, col ≠ b ∧ ∀ x, G.Adj u x → c x ≠ col := by by_contra hcon push Not at hcon have hsub : (Finset.univ : Finset (Fin K)) ⊆ insert b ((G.neighborFinset u).image (fun x => c x)) := by intro col _ by_cases hb : col = b · simp [hb] · obtain ⟨x, hx, hcx⟩ := hcon col hb exact Finset.mem_insert_of_mem (Finset.mem_image.mpr ⟨x, by simpa using hx, hcx⟩) have h1 := Finset.card_le_card hsub have h2 := Finset.card_insert_le b ((G.neighborFinset u).image (fun x => c x)) have h3 := Finset.card_image_le (s := G.neighborFinset u) (f := fun x => c x) have h4 : (G.neighborFinset u).card ≤ G.maxDegree := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact G.degree_le_maxDegree u simp only [Finset.card_univ, Fintype.card_fin] at h1 omega theorem clear_nbrs (hk : G.maxDegree + 2 ≤ K) (β : G.Coloring (Fin K)) (v : V) (t : Finset V) : ∀ m (c : G.Coloring (Fin K)), ((G.neighborFinset v).filter (fun u => c u = β v)).card ≤ m → (∀ w, w ∉ insert v t → c w = β w) → ∃ c1 : G.Coloring (Fin K), (simple_graph_reconfiguration_graph G K).Reachable c c1 ∧ (∀ w, w ∉ insert v t → c1 w = β w) ∧ (∀ u, G.Adj v u → c1 u ≠ β v) := by intro m induction m with | zero => intro c hm hc refine ⟨c, SimpleGraph.Reachable.refl _, hc, fun u hu hcu => ?_⟩ rw [Nat.le_zero, Finset.card_eq_zero, Finset.filter_eq_empty_iff] at hm exact hm (by simpa using hu) hcu | succ m ih => intro c hm hc by_cases hle : ((G.neighborFinset v).filter (fun u => c u = β v)).card ≤ m · exact ih c hle hc obtain ⟨u, hu⟩ : ((G.neighborFinset v).filter (fun u => c u = β v)).Nonempty := by rw [← Finset.card_pos]; omega simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset] at hu have hut : u ∈ insert v t := by by_contra hnot have := hc u hnot exact β.valid hu.1 (hu.2.symm.trans this) obtain ⟨col, hcolb, hcol⟩ := exists_free_colour hk c u (β v) obtain ⟨c', hc'eq, hreach⟩ := reach_update c u col hcol have hsub : (G.neighborFinset v).filter (fun x => c' x = β v) ⊆ ((G.neighborFinset v).filter (fun x => c x = β v)).erase u := by intro x hx simp only [Finset.mem_filter, Finset.mem_erase] at hx ⊢ rw [hc'eq] at hx by_cases hxu : x = u · subst hxu; simp at hx; exact absurd hx.2 hcolb · simp only [Function.update_of_ne hxu] at hx exact ⟨hxu, hx⟩ have hcard := Finset.card_le_card hsub rw [Finset.card_erase_of_mem (by simp [hu.1, hu.2])] at hcard have hc' : ∀ w, w ∉ insert v t → c' w = β w := by intro w hw rw [hc'eq] have hwu : w ≠ u := fun h => hw (h ▸ hut) simp only [Function.update_of_ne hwu]; exact hc w hw obtain ⟨c1, h1, h2, h3⟩ := ih c' (by omega) hc' exact ⟨c1, hreach.trans h1, h2, h3⟩ theorem reach_beta (hk : G.maxDegree + 2 ≤ K) (β : G.Coloring (Fin K)) (s : Finset V) : ∀ c : G.Coloring (Fin K), (∀ w, w ∉ s → c w = β w) → (simple_graph_reconfiguration_graph G K).Reachable c β := by induction s using Finset.induction_on with | empty => intro c hc have : c = β := RelHom.ext fun x => hc x (Finset.notMem_empty x) rw [this] | insert v t hv ih => intro c hc obtain ⟨c1, hr1, hc1, hnb⟩ := clear_nbrs hk β v t _ c le_rfl hc obtain ⟨c2, hc2eq, hr2⟩ := reach_update c1 v (β v) (fun x hx => hnb x hx) refine hr1.trans (hr2.trans (ih c2 fun w hw => ?_)) rw [hc2eq] by_cases hwv : w = v · subst hwv; simp · simp only [Function.update_of_ne hwv] exact hc1 w (by simp [hwv, hw]) theorem recolour_connected (hk : G.maxDegree + 2 ≤ K) (a b : G.Coloring (Fin K)) : (simple_graph_reconfiguration_graph G K).Reachable a b := reach_beta hk b Finset.univ a (fun w hw => absurd (Finset.mem_univ w) hw) end conn
Any walk from α₅ to β₅ in the 10-reconfiguration graph of G₅ has length at least 31.
Let n(p) = |steps(w, p)|. Claims 1 and 2 ensure that n satisfies the hypotheses of the counting theorem count. Together with sum_steps_le, this gives 31 ≤ ∑ p, n(p) ≤ length(w).
uses
claim2,claim1,count,sum_steps_letheorem walk_len (w : (simple_graph_reconfiguration_graph G5 10).Walk α5 β5) : 31 ≤ w.length := by have hA : ∀ i j : Fin 5, i ≠ j → (steps w (i, i)).card = 1 → (steps w (j, j)).card = 1 → 2 ≤ (steps w (i, j)).card ∨ 2 ≤ (steps w (j, i)).card := by intro i j hij h1 h2 by_contra hne push Not at hne have g3 := steps_nonempty w (α5_ne_β5 (i, j)) have g4 := steps_nonempty w (α5_ne_β5 (j, i)) obtain ⟨s₁, hs₁⟩ := Finset.card_eq_one.mp h1 obtain ⟨s₂, hs₂⟩ := Finset.card_eq_one.mp h2 obtain ⟨t₁, ht₁⟩ := Finset.card_eq_one.mp (by omega : (steps w (i, j)).card = 1) obtain ⟨t₂, ht₂⟩ := Finset.card_eq_one.mp (by omega : (steps w (j, i)).card = 1) exact claim2 w hij hs₁ hs₂ ht₁ ht₂ have := count (fun p => (steps w p).card) (fun p => steps_nonempty w (α5_ne_β5 p)) hA (fun i h => claim1 w h) exact this.trans (sum_steps_le w)
G₅ certifies that Δ = 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
G₅ has Δ = 8 and 25 vertices. By recolour_connected, the 10-reconfiguration graph is connected, so the distance between α₅ and β₅ equals the length of a shortest walk, which is at least 31 by walk_len. Therefore diam(R₁₀(G₅)) ≥ 31 > 25 + 5 ≥ |V(G₅)| + ν(G₅).
uses
G5_maxDegree,recolour_connected,walk_len,SimpleGraph.dist_le_diam,G5_matchingtheorem le_eight_aux : simple_graph_reconfiguration_diam_gt_matching 8 := by refine ⟨Fin 5 × Fin 5, inferInstance, inferInstance, G5, inferInstance, G5_maxDegree, ?_⟩ have : Nonempty (G5.Coloring (Fin 10)) := ⟨α5⟩ have : Finite (G5.Coloring (Fin 10)) := Finite.of_injective _ DFunLike.coe_injective have hconn : (simple_graph_reconfiguration_graph G5 (8 + 2)).Connected := ⟨fun a b => recolour_connected (by rw [G5_maxDegree]) a b⟩ have hne := SimpleGraph.connected_iff_ediam_ne_top.mp hconn obtain ⟨w, hw⟩ := hconn.exists_walk_length_eq_dist α5 β5 have h31 : 31 ≤ (simple_graph_reconfiguration_graph G5 (8 + 2)).diam := ((walk_len w).trans hw.le).trans (SimpleGraph.dist_le_diam hne) have hcard : Fintype.card (Fin 5 × Fin 5) = 25 := by simp rw [hcard] calc ((25 : ℕ) : ℕ∞) + graph_matching_num G5 ≤ 25 + 5 := add_le_add le_rfl G5_matching _ < 31 := by norm_num _ ≤ _ := by exact_mod_cast h31 end Op1611LeEight
The natural number 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
The theorem follows directly from the construction and properties of G₅ established in le_eight_aux.
uses
Op1611LeEight.le_eight_auxtheorem op_1611_min_max_degree_le_eight : simple_graph_reconfiguration_diam_gt_matching 8 := by exact Op1611LeEight.le_eight_aux
graph_matching_num_le_vertex_cover_num- The maximum size of a matching is bounded above by the minimum size of a vertex cover (weak duality).
Set.encard_coe_eq_coe_finsetCard- The extended natural cardinality of a coerced finite set equals the cardinality of the finset.
steps_unique- At each step of a reconfiguration walk, at most one vertex changes color; hence any step index belongs to the change set of at most one vertex.
Finset.card_biUnion- The cardinality of a disjoint union of finite sets is the sum of the cardinalities of the components.
Finset.card_le_card- If a finite set is a subset of another, its cardinality is less than or equal to that of the superset.
Nat.le_induction- Mathematical induction on natural numbers starting from a base index.
getVert_const- A vertex maintains its color across any time interval during which it experiences no color change steps.
steps_one- If a vertex changes color at exactly one step s, it retains its initial color for k ≤ s and assumes its final color for k > s.
steps_two- If a vertex changes color at exactly two steps s₁ < s₂, it assumes a unique intermediate color distinct from both its start and end colors for s₁ < k ≤ s₂.
step_ne- Distinct vertices cannot change color at the same step of a reconfiguration walk.
prop_at- Adjacent vertices have distinct colors at every step along any valid recoloring walk.
adj_x_y- Diagonal vertex (i, i) is adjacent to off-diagonal vertex (i, j) whenever i ≠ j.
adj_x_y'- Diagonal vertex (i, i) is adjacent to off-diagonal vertex (j, i) whenever j ≠ i.
claim1_aux- If diagonal vertex (i, i) changes color twice, its intermediate color identifies an index j ≠ i such that (i, j) or (j, i) changes color at least twice.
bonus_sum- For any boolean function f on Fin 5, the sum of bonusF f i over all five vertices is at least 11.
count_key- For each index i, the sum of changes on incident off-diagonal vertices is at least 10 plus the bonus term determined by whether (i, i) changes once, twice, or more.
count- Any change count assignment on the 25 vertices satisfying the degree and transition constraints sums to at least 31.
exists_free_colour- When the number of colors satisfies K ≥ Δ(G) + 2, every vertex has an available color distinct from a target color b and distinct from all its neighbors' colors.
reach_update- If no neighbor of vertex u has color col, updating the color of u to col yields a valid coloring reachable in one step.
clear_nbrs- Neighbors of a vertex v currently colored β(v) can be recolored one by one to other available colors without altering colors outside a designated set.
reach_beta- Any coloring agreeing with β outside a finite set s can reach β in the reconfiguration graph by sequentially recoloring vertices in s.
recolour_connected- If K ≥ Δ(G) + 2, the reconfiguration graph of K-colorings is connected (any two colorings are connected by a walk).
claim2- It is impossible for two diagonal vertices (i, i), (j, j) and their connecting off-diagonal vertices (i, j), (j, i) to all change color only once.
claim1- If diagonal vertex (i, i) changes color exactly twice, some incident off-diagonal vertex must change color at least twice.
sum_steps_le- The sum over all vertices of the number of color changes each undergoes is at most the total length of the reconfiguration walk.
G5_maxDegree- The maximum degree of the graph G₅ is equal to 8.
walk_len- Every walk in the 10-reconfiguration graph of G₅ connecting α₅ to β₅ has length at least 31.
SimpleGraph.dist_le_diam- The graph distance between any two vertices in a connected graph is bounded above by the graph diameter.
G5_matching- The matching number of G₅ is at most 5.
Op1611LeEight.le_eight_aux- The natural number 8 satisfies the reconfiguration diameter-matching property via the witness graph G₅.
- The degree bounds on G₅, the inequality α₅ ≠ β₅, and the bonus sum inequality ∑ i, bonusF f i ≥ 11 for all boolean functions f are established by exhaustive finite verification using the `decide` tactic with kernel computation.
- The validity of the colorings α₅ and β₅ and the transition impossibility results in Claims 1 and 2 rely on extensive case analysis and linear arithmetic automation (`omega`) to confirm that adjacent vertices never share a color.
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.
Lean’s trace was cut to the first 400 of 969 tactics.
open Finsetnamespace Op1611LeEight/-- The 1-subdivision of the doubled K₅: `(i,i)` is `xᵢ`, `(i,j)` with `i ≠ j` is `y_ij`,adjacent to `xᵢ` and `xⱼ`. -/def G5 : SimpleGraph (Fin 5 × Fin 5) where Adj p q := (p.1 = p.2 ∧ q.1 ≠ q.2 ∧ (q.1 = p.1 ∨ q.2 = p.1)) ∨ (q.1 = q.2 ∧ p.1 ≠ p.2 ∧ (p.1 = q.1 ∨ p.2 = q.1)) symm := ⟨fun p q h => by tauto⟩ loopless := ⟨fun p h => by rcases h with ⟨h1, h2, _⟩ | ⟨h1, h2, _⟩ <;> exact h2 h1⟩instance op1611LeEight_G5_decAdj : DecidableRel G5.Adj := fun p q => inferInstanceAs (Decidable ((p.1 = p.2 ∧ q.1 ≠ q.2 ∧ (q.1 = p.1 ∨ q.2 = p.1)) ∨ (q.1 = q.2 ∧ p.1 ≠ p.2 ∧ (p.1 = q.1 ∨ p.2 = q.1))))theorem G5_degree_le : ∀ p, G5.degree p ≤ 8 := by decide +kerneltheorem G5_degree_x : G5.degree (0, 0) = 8 := by decide +kerneltheorem G5_maxDegree : G5.maxDegree = 8 := le_antisymm (G5.maxDegree_le_of_forall_degree_le 8 G5_degree_le) (G5_degree_x ▸ G5.degree_le_maxDegree _)theorem G5_matching : graph_matching_num G5 ≤ 5 := by refine (graph_matching_num_le_vertex_cover_num G5).trans ?_ have hc : G5.IsVertexCover {p | p.1 = p.2} := by intro p q h change _ ∨ _ at h rcases h with h | h · exact Or.inl h.1 · exact Or.inr h.1 refine hc.vertexCoverNum_le.trans ?_ have : ({p | p.1 = p.2} : Set (Fin 5 × Fin 5)) = ((Finset.univ.filter fun p : Fin 5 × Fin 5 => p.1 = p.2 : Finset _) : Set _) := by ext p; simp rw [this, Set.encard_coe_eq_coe_finsetCard] have h5 : (Finset.univ.filter fun p : Fin 5 × Fin 5 => p.1 = p.2).card = 5 := by decide rw [h5]; rfl/-- Colouring α: `xᵢ ↦ aᵢ = i`, `y_ij ↦ bᵢ = 5 + i`. -/def α5 : G5.Coloring (Fin 10) := SimpleGraph.Coloring.mk (fun p => ⟨if p.1 = p.2 then p.1.val else 5 + p.1.val, by split <;> omega⟩) (by intro p q h heq have hv := congrArg Fin.val heq dsimp only at hv change _ ∨ _ at h rcases h with ⟨h1, h2, h3⟩ | ⟨h1, h2, h3⟩ <;> simp only [Fin.ext_iff, ne_eq] at h1 h2 h3 <;> split_ifs at hv <;> simp only [Fin.ext_iff] at * <;> omega)/-- Colouring β: `xᵢ ↦ bᵢ = 5 + i`, `y_ij ↦ aⱼ = j`. -/def β5 : G5.Coloring (Fin 10) := SimpleGraph.Coloring.mk (fun p => ⟨if p.1 = p.2 then 5 + p.1.val else p.2.val, by split <;> omega⟩) (by intro p q h heq have hv := congrArg Fin.val heq dsimp only at hv change _ ∨ _ at h rcases h with ⟨h1, h2, h3⟩ | ⟨h1, h2, h3⟩ <;> simp only [Fin.ext_iff, ne_eq] at h1 h2 h3 <;> split_ifs at hv <;> simp only [Fin.ext_iff] at * <;> omega)theorem α5_ne_β5 : ∀ p, α5 p ≠ β5 p := by decide +kernelvariable {V : Type} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {K : ℕ}/-- Steps of a recolouring walk at which vertex `v` changes. -/def steps {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) (v : V) : Finset ℕ := (Finset.range w.length).filter (fun k => w.getVert k v ≠ w.getVert (k + 1) v)theorem steps_unique {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {u v : V} {s : ℕ} (hu : s ∈ steps w u) (hv : s ∈ steps w v) : u = v := by simp only [steps, Finset.mem_filter, Finset.mem_range] at hu hv obtain ⟨x, _, hx⟩ := w.adj_getVert_succ hu.1 exact (hx u hu.2).trans (hx v hv.2).symmtheorem sum_steps_le {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) : ∑ v, (steps w v).card ≤ w.length := by rw [← Finset.card_biUnion] · calc _ ≤ (Finset.range w.length).card := by apply Finset.card_le_card intro s hs simp only [Finset.mem_biUnion] at hs obtain ⟨v, _, hv⟩ := hs simp only [steps, Finset.mem_filter] at hv exact hv.1 _ = _ := Finset.card_range _ · intro u _ v _ huv exact Finset.disjoint_left.mpr fun _ hu hv => huv (steps_unique w hu hv)theorem getVert_const {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) (v : V) (k : ℕ) : ∀ k', k ≤ k' → (∀ s, k ≤ s → s < k' → s ∉ steps w v) → w.getVert k v = w.getVert k' v := by intro k' hk induction k', hk using Nat.le_induction with | base => intro _; rfl | succ n hn ih => intro h rw [ih (fun s h1 h2 => h s h1 (by omega))] by_contra hne by_cases hL : n < w.length · exact h n hn (by omega) (by simp [steps, hL, hne]) · apply hne rw [w.getVert_of_length_le (by omega), w.getVert_of_length_le (by omega)]theorem steps_nonempty {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {v : V} (h : a v ≠ b v) : 1 ≤ (steps w v).card := by rw [Nat.one_le_iff_ne_zero, Ne, Finset.card_eq_zero] intro h0 apply h have := getVert_const w v 0 w.length (Nat.zero_le _) (by simp [h0]) simpa using thistheorem steps_one {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {v : V} {s : ℕ} (h : steps w v = {s}) (k : ℕ) : w.getVert k v = if k ≤ s then a v else b v := by have hs : s < w.length := by have : s ∈ steps w v := by simp [h] simp only [steps, Finset.mem_filter, Finset.mem_range] at this; exact this.1 split_ifs with hk · have := getVert_const w v 0 k (Nat.zero_le _) (by intro t _ ht; simp [h]; omega) simpa using this.symm · by_cases hkL : k ≤ w.length · have := getVert_const w v k w.length hkL (by intro t ht _; simp [h]; omega) simpa using this · rw [w.getVert_of_length_le (by omega)]theorem steps_two {a b : G.Coloring (Fin K)} (w : (simple_graph_reconfiguration_graph G K).Walk a b) {v : V} {s₁ s₂ : ℕ} (h : steps w v = {s₁, s₂}) (h12 : s₁ < s₂) : ∃ m, m ≠ a v ∧ m ≠ b v ∧ ∀ k, w.getVert k v = if k ≤ s₁ then a v else if k ≤ s₂ then m else b v := by have hm1 : s₁ ∈ steps w v := by simp [h] have hm2 : s₂ ∈ steps w v := by simp [h] simp only [steps, Finset.mem_filter, Finset.mem_range] at hm1 hm2 have e0 : ∀ k, k ≤ s₁ → w.getVert k v = a v := fun k hk => by have := getVert_const w v 0 k (Nat.zero_le _) (by intro t _ ht; simp [h]; omega) simpa using this.symm have e1 : ∀ k, s₁ < k → k ≤ s₂ → w.getVert k v = w.getVert (s₁ + 1) v := fun k hk1 hk2 => by have := getVert_const w v (s₁ + 1) k hk1 (by intro t ht1 ht2; simp [h]; omega) exact this.symm have e2 : ∀ k, s₂ < k → w.getVert k v = b v := fun k hk => by by_cases hkL : k ≤ w.length · have := getVert_const w v k w.length hkL (by intro t ht _; simp [h]; omega) simpa using this · rw [w.getVert_of_length_le (by omega)] refine ⟨w.getVert (s₁ + 1) v, ?_, ?_, ?_⟩ · rw [← e0 s₁ le_rfl]; exact fun hh => hm1.2 hh.symm · rw [← e2 (s₂ + 1) (by omega), ← e1 s₂ h12 le_rfl]; exact hm2.2 · intro k split_ifs with ha hb · exact e0 k ha · exact e1 k (by omega) hb · exact e2 k (by omega)section claimstheorem α5_val (p : Fin 5 × Fin 5) : (α5 p).val = if p.1 = p.2 then p.1.val else 5 + p.1.val := rfltheorem β5_val (p : Fin 5 × Fin 5) : (β5 p).val = if p.1 = p.2 then 5 + p.1.val else p.2.val := rfltheorem adj_x_y {i j : Fin 5} (h : i ≠ j) : G5.Adj (i, i) (i, j) := Or.inl ⟨rfl, h, Or.inl rfl⟩theorem adj_x_y' {i j : Fin 5} (h : j ≠ i) : G5.Adj (i, i) (j, i) := Or.inl ⟨rfl, h, Or.inr rfl⟩variable (w : (simple_graph_reconfiguration_graph G5 10).Walk α5 β5)theorem prop_at {p q : Fin 5 × Fin 5} (hadj : G5.Adj p q) (k : ℕ) : ((w.getVert k) p).val ≠ ((w.getVert k) q).val := fun h => (w.getVert k).valid hadj (Fin.ext h)theorem step_ne {p q : Fin 5 × Fin 5} (hpq : p ≠ q) {s t : ℕ} (hs : s ∈ steps w p) (ht : t ∈ steps w q) : s ≠ t := by rintro rfl; exact hpq (steps_unique w hs ht)theorem claim2 {i j : Fin 5} (hij : i ≠ j) {s₁ s₂ t₁ t₂ : ℕ} (h1 : steps w (i, i) = {s₁}) (h2 : steps w (j, j) = {s₂}) (h3 : steps w (i, j) = {t₁}) (h4 : steps w (j, i) = {t₂}) : False := by have hji : j ≠ i := Ne.symm hij have hi : (i : ℕ) ≠ j := fun h => hij (Fin.ext h) have d1 : t₁ ≠ s₁ := step_ne w (p := (i, j)) (q := (i, i)) (by simp [hij, hji]) (by simp [h3]) (by simp [h1]) have d2 : t₁ ≠ s₂ := step_ne w (p := (i, j)) (q := (j, j)) (by simp [hij, hji]) (by simp [h3]) (by simp [h2]) have d3 : t₂ ≠ s₁ := step_ne w (p := (j, i)) (q := (i, i)) (by simp [hij, hji]) (by simp [h4]) (by simp [h1]) have d4 : t₂ ≠ s₂ := step_ne w (p := (j, i)) (q := (j, j)) (by simp [hij, hji]) (by simp [h4]) (by simp [h2]) have c1 := prop_at w (adj_x_y hij) t₁ have c2 := prop_at w (adj_x_y' hij) (t₁ + 1) have c3 := prop_at w (adj_x_y hji) t₂ have c4 := prop_at w (adj_x_y' hji) (t₂ + 1) rw [steps_one w h1, steps_one w h3] at c1 rw [steps_one w h2, steps_one w h3] at c2 rw [steps_one w h2, steps_one w h4] at c3 rw [steps_one w h1, steps_one w h4] at c4 simp only [apply_ite Fin.val, α5_val, β5_val, hij, hji, if_true, if_false] at c1 c2 c3 c4 split_ifs at c1 c2 c3 c4 <;> omegatheorem claim1_aux {i : Fin 5} {s₁ s₂ : ℕ} (h : steps w (i, i) = {s₁, s₂}) (h12 : s₁ < s₂) : ∃ j, j ≠ i ∧ (2 ≤ (steps w (i, j)).card ∨ 2 ≤ (steps w (j, i)).card) := by obtain ⟨m, hm1, hm2, hf⟩ := steps_two w h h12 have hm1' : m.val ≠ i.val := fun e => hm1 (Fin.ext (by simp [α5_val, e])) have hm2' : m.val ≠ 5 + i.val := fun e => hm2 (Fin.ext (by simp [β5_val, e])) have hs1 : s₁ ∈ steps w (i, i) := by simp [h] have hs2 : s₂ ∈ steps w (i, i) := by simp [h] by_cases hm : m.val < 5 · set j : Fin 5 := ⟨m.val, hm⟩ with hjdef have hij : i ≠ j := fun e => hm1' (by rw [e]) refine ⟨j, Ne.symm hij, Or.inl ?_⟩ by_contra hlt have hge := steps_nonempty w (α5_ne_β5 (i, j)) obtain ⟨t, ht⟩ := Finset.card_eq_one.mp (by omega : (steps w (i, j)).card = 1) have htm : t ∈ steps w (i, j) := by simp [ht] have d1 := step_ne w (p := (i, j)) (q := (i, i)) (by simp [hij, Ne.symm hij]) htm hs1 have d2 := step_ne w (p := (i, j)) (q := (i, i)) (by simp [hij, Ne.symm hij]) htm hs2 have c1 := prop_at w (adj_x_y hij) (s₁ + 1) have c2 := prop_at w (adj_x_y hij) (t + 1) have c3 := prop_at w (adj_x_y hij) (s₂ + 1) rw [hf, steps_one w ht] at c1 c2 c3 simp only [apply_ite Fin.val, α5_val, β5_val, hij, if_true, if_false, hjdef] at c1 c2 c3 split_ifs at c1 c2 c3 <;> omega · set j : Fin 5 := ⟨m.val - 5, by omega⟩ with hjdef have hji : j ≠ i := fun e => hm2' (by rw [← e]; simp [hjdef]; omega) refine ⟨j, hji, Or.inr ?_⟩ by_contra hlt have hge := steps_nonempty w (α5_ne_β5 (j, i)) obtain ⟨t, ht⟩ := Finset.card_eq_one.mp (by omega : (steps w (j, i)).card = 1) have htm : t ∈ steps w (j, i) := by simp [ht] have d1 := step_ne w (p := (j, i)) (q := (i, i)) (by simp [hji, Ne.symm hji]) htm hs1 have c1 := prop_at w (adj_x_y' hji) (s₁ + 1) have c2 := prop_at w (adj_x_y' hji) (t + 1) rw [hf, steps_one w ht] at c1 c2 simp only [apply_ite Fin.val, α5_val, β5_val, hji, if_true, if_false, hjdef] at c1 c2 split_ifs at c1 c2 <;> omegatheorem claim1 {i : Fin 5} (h : (steps w (i, i)).card = 2) : ∃ j, j ≠ i ∧ (2 ≤ (steps w (i, j)).card ∨ 2 ≤ (steps w (j, i)).card) := by obtain ⟨x, y, hxy, he⟩ := Finset.card_eq_two.mp h rcases lt_or_gt_of_ne hxy with hlt | hlt · exact claim1_aux w he hlt · exact claim1_aux w (he.trans (Finset.pair_comm x y)) hltend claimsdef bonusF (f : Fin 5 → Bool) (i : Fin 5) : ℕ := if f i then ((Finset.univ.erase i).filter (fun j => f j = true)).card else 3theorem bonus_sum : ∀ f : Fin 5 → Bool, 11 ≤ ∑ i, bonusF f i := by decidetheorem count_key (n : Fin 5 × Fin 5 → ℕ) (h1 : ∀ p, 1 ≤ n p) (hA : ∀ i j, i ≠ j → n (i, i) = 1 → n (j, j) = 1 → 2 ≤ n (i, j) ∨ 2 ≤ n (j, i)) (hB : ∀ i, n (i, i) = 2 → ∃ j, j ≠ i ∧ (2 ≤ n (i, j) ∨ 2 ≤ n (j, i))) (i : Fin 5) : 10 + bonusF (fun j => decide (n (j, j) = 1)) i ≤ ∑ j, (n (i, j) + n (j, i)) := by rw [← Finset.add_sum_erase _ _ (Finset.mem_univ i)] have hc : (Finset.univ.erase i).card = 4 := by simp have base : ∀ j ∈ Finset.univ.erase i, 2 ≤ n (i, j) + n (j, i) := fun j _ => by have := h1 (i, j); have := h1 (j, i); omega unfold bonusF by_cases hi1 : n (i, i) = 1 · simp only [hi1, decide_true, if_true] have : ∑ j ∈ Finset.univ.erase i, (2 + if n (j, j) = 1 then 1 else 0) ≤ ∑ j ∈ Finset.univ.erase i, (n (i, j) + n (j, i)) := by apply Finset.sum_le_sum intro j hj have hb := base j hj have := h1 (i, j); have := h1 (j, i) have hji : j ≠ i := Finset.ne_of_mem_erase hj split_ifs with hj1 · rcases hA i j (Ne.symm hji) hi1 hj1 with h | h <;> omega · omega rw [Finset.sum_add_distrib, Finset.sum_const, hc, Finset.sum_boole] at this simp only [smul_eq_mul, Nat.cast_id] at this have e : ((Finset.univ.erase i).filter (fun j => decide (n (j, j) = 1) = true)) = ((Finset.univ.erase i).filter (fun j => n (j, j) = 1)) := by ext j; simp rw [e]; omega · have hd : decide (n (i, i) = 1) = false := by simp [hi1] simp only [hd, if_false, Bool.false_eq_true] have hii := h1 (i, i) by_cases hi2 : n (i, i) = 2 · obtain ⟨j0, hj0, hj0'⟩ := hB i hi2 have : ∑ j ∈ Finset.univ.erase i, (2 + if j = j0 then 1 else 0) ≤ ∑ j ∈ Finset.univ.erase i, (n (i, j) + n (j, i)) := by apply Finset.sum_le_sum intro j hj have hb := base j hj have := h1 (i, j); have := h1 (j, i) split_ifs with hj1 · subst hj1; rcases hj0' with h | h <;> omega · omega rw [Finset.sum_add_distrib, Finset.sum_const, hc, Finset.sum_ite_eq' (Finset.univ.erase i) j0 (fun _ => 1)] at this simp only [Finset.mem_erase, ne_eq, hj0, not_false_eq_true, Finset.mem_univ, and_self, if_true, smul_eq_mul] at this omega · have : ∑ j ∈ Finset.univ.erase i, 2 ≤ ∑ j ∈ Finset.univ.erase i, (n (i, j) + n (j, i)) := Finset.sum_le_sum base rw [Finset.sum_const, hc, smul_eq_mul] at this omegatheorem count (n : Fin 5 × Fin 5 → ℕ) (h1 : ∀ p, 1 ≤ n p) (hA : ∀ i j, i ≠ j → n (i, i) = 1 → n (j, j) = 1 → 2 ≤ n (i, j) ∨ 2 ≤ n (j, i)) (hB : ∀ i, n (i, i) = 2 → ∃ j, j ≠ i ∧ (2 ≤ n (i, j) ∨ 2 ≤ n (j, i))) : 31 ≤ ∑ p, n p := by have e1 : ∑ p, n p = ∑ i, ∑ j, n (i, j) := Fintype.sum_prod_type _ have e2 : ∑ i, ∑ j, n (j, i) = ∑ i, ∑ j, n (i, j) := Finset.sum_comm have hsum : ∑ i, (10 + bonusF (fun j => decide (n (j, j) = 1)) i) ≤ ∑ i, ∑ j, (n (i, j) + n (j, i)) := Finset.sum_le_sum fun i _ => count_key n h1 hA hB i simp only [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hsum have hb := bonus_sum (fun j => decide (n (j, j) = 1)) omegasection connvariable {V : Type} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {K : ℕ}theorem reach_update (c : G.Coloring (Fin K)) (u : V) (col : Fin K) (hv : ∀ x, G.Adj u x → c x ≠ col) : ∃ c' : G.Coloring (Fin K), (∀ x, c' x = Function.update c u col x) ∧ (simple_graph_reconfiguration_graph G K).Reachable c c' := by let c' : G.Coloring (Fin K) := SimpleGraph.Coloring.mk (Function.update c u col) (by intro a b hab by_cases ha : a = u · subst ha have hb : b ≠ a := (G.ne_of_adj hab).symm simp only [Function.update_self, Function.update_of_ne hb] exact (hv b hab).symm · by_cases hb : b = u · subst hb simp only [Function.update_self, Function.update_of_ne ha] exact hv a hab.symm · simp only [Function.update_of_ne ha, Function.update_of_ne hb] exact c.valid hab) refine ⟨c', fun x => rfl, ?_⟩ by_cases hc : c u = col · have : c = c' := by refine RelHom.ext fun x => ?_ show c x = Function.update c u col x by_cases hx : x = u · subst hx; simp [hc] · simp [Function.update_of_ne hx] rw [this] · apply SimpleGraph.Adj.reachable refine ⟨u, ?_, ?_⟩ · show c u ≠ Function.update c u col u simpa using hc · intro y hy by_contra hyu apply hy show c y = Function.update c u col y simp [Function.update_of_ne hyu]theorem exists_free_colour (hk : G.maxDegree + 2 ≤ K) (c : G.Coloring (Fin K)) (u : V) (b : Fin K) : ∃ col : Fin K, col ≠ b ∧ ∀ x, G.Adj u x → c x ≠ col := by by_contra hcon push Not at hcon have hsub : (Finset.univ : Finset (Fin K)) ⊆ insert b ((G.neighborFinset u).image (fun x => c x)) := by intro col _ by_cases hb : col = b · simp [hb] · obtain ⟨x, hx, hcx⟩ := hcon col hb exact Finset.mem_insert_of_mem (Finset.mem_image.mpr ⟨x, by simpa using hx, hcx⟩) have h1 := Finset.card_le_card hsub have h2 := Finset.card_insert_le b ((G.neighborFinset u).image (fun x => c x)) have h3 := Finset.card_image_le (s := G.neighborFinset u) (f := fun x => c x) have h4 : (G.neighborFinset u).card ≤ G.maxDegree := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact G.degree_le_maxDegree u simp only [Finset.card_univ, Fintype.card_fin] at h1 omegatheorem clear_nbrs (hk : G.maxDegree + 2 ≤ K) (β : G.Coloring (Fin K)) (v : V) (t : Finset V) : ∀ m (c : G.Coloring (Fin K)), ((G.neighborFinset v).filter (fun u => c u = β v)).card ≤ m → (∀ w, w ∉ insert v t → c w = β w) → ∃ c1 : G.Coloring (Fin K), (simple_graph_reconfiguration_graph G K).Reachable c c1 ∧ (∀ w, w ∉ insert v t → c1 w = β w) ∧ (∀ u, G.Adj v u → c1 u ≠ β v) := by intro m induction m with | zero => intro c hm hc refine ⟨c, SimpleGraph.Reachable.refl _, hc, fun u hu hcu => ?_⟩ rw [Nat.le_zero, Finset.card_eq_zero, Finset.filter_eq_empty_iff] at hm exact hm (by simpa using hu) hcu | succ m ih => intro c hm hc by_cases hle : ((G.neighborFinset v).filter (fun u => c u = β v)).card ≤ m · exact ih c hle hc obtain ⟨u, hu⟩ : ((G.neighborFinset v).filter (fun u => c u = β v)).Nonempty := by rw [← Finset.card_pos]; omega simp only [Finset.mem_filter, SimpleGraph.mem_neighborFinset] at hu have hut : u ∈ insert v t := by by_contra hnot have := hc u hnot exact β.valid hu.1 (hu.2.symm.trans this) obtain ⟨col, hcolb, hcol⟩ := exists_free_colour hk c u (β v) obtain ⟨c', hc'eq, hreach⟩ := reach_update c u col hcol have hsub : (G.neighborFinset v).filter (fun x => c' x = β v) ⊆ ((G.neighborFinset v).filter (fun x => c x = β v)).erase u := by intro x hx simp only [Finset.mem_filter, Finset.mem_erase] at hx ⊢ rw [hc'eq] at hx by_cases hxu : x = u · subst hxu; simp at hx; exact absurd hx.2 hcolb · simp only [Function.update_of_ne hxu] at hx exact ⟨hxu, hx⟩ have hcard := Finset.card_le_card hsub rw [Finset.card_erase_of_mem (by simp [hu.1, hu.2])] at hcard have hc' : ∀ w, w ∉ insert v t → c' w = β w := by intro w hw rw [hc'eq] have hwu : w ≠ u := fun h => hw (h ▸ hut) simp only [Function.update_of_ne hwu]; exact hc w hw obtain ⟨c1, h1, h2, h3⟩ := ih c' (by omega) hc' exact ⟨c1, hreach.trans h1, h2, h3⟩theorem reach_beta (hk : G.maxDegree + 2 ≤ K) (β : G.Coloring (Fin K)) (s : Finset V) : ∀ c : G.Coloring (Fin K), (∀ w, w ∉ s → c w = β w) → (simple_graph_reconfiguration_graph G K).Reachable c β := by induction s using Finset.induction_on with | empty => intro c hc have : c = β := RelHom.ext fun x => hc x (Finset.notMem_empty x) rw [this] | insert v t hv ih => intro c hc obtain ⟨c1, hr1, hc1, hnb⟩ := clear_nbrs hk β v t _ c le_rfl hc obtain ⟨c2, hc2eq, hr2⟩ := reach_update c1 v (β v) (fun x hx => hnb x hx) refine hr1.trans (hr2.trans (ih c2 fun w hw => ?_)) rw [hc2eq] by_cases hwv : w = v · subst hwv; simp · simp only [Function.update_of_ne hwv] exact hc1 w (by simp [hwv, hw])theorem recolour_connected (hk : G.maxDegree + 2 ≤ K) (a b : G.Coloring (Fin K)) : (simple_graph_reconfiguration_graph G K).Reachable a b := reach_beta hk b Finset.univ a (fun w hw => absurd (Finset.mem_univ w) hw)end conntheorem walk_len (w : (simple_graph_reconfiguration_graph G5 10).Walk α5 β5) : 31 ≤ w.length := by have hA : ∀ i j : Fin 5, i ≠ j → (steps w (i, i)).card = 1 → (steps w (j, j)).card = 1 → 2 ≤ (steps w (i, j)).card ∨ 2 ≤ (steps w (j, i)).card := by intro i j hij h1 h2 by_contra hne push Not at hne have g3 := steps_nonempty w (α5_ne_β5 (i, j)) have g4 := steps_nonempty w (α5_ne_β5 (j, i)) obtain ⟨s₁, hs₁⟩ := Finset.card_eq_one.mp h1 obtain ⟨s₂, hs₂⟩ := Finset.card_eq_one.mp h2 obtain ⟨t₁, ht₁⟩ := Finset.card_eq_one.mp (by omega : (steps w (i, j)).card = 1) obtain ⟨t₂, ht₂⟩ := Finset.card_eq_one.mp (by omega : (steps w (j, i)).card = 1) exact claim2 w hij hs₁ hs₂ ht₁ ht₂ have := count (fun p => (steps w p).card) (fun p => steps_nonempty w (α5_ne_β5 p)) hA (fun i h => claim1 w h) exact this.trans (sum_steps_le w)theorem le_eight_aux : simple_graph_reconfiguration_diam_gt_matching 8 := by refine ⟨Fin 5 × Fin 5, inferInstance, inferInstance, G5, inferInstance, G5_maxDegree, ?_⟩ have : Nonempty (G5.Coloring (Fin 10)) := ⟨α5⟩ have : Finite (G5.Coloring (Fin 10)) := Finite.of_injective _ DFunLike.coe_injective have hconn : (simple_graph_reconfiguration_graph G5 (8 + 2)).Connected := ⟨fun a b => recolour_connected (by rw [G5_maxDegree]) a b⟩ have hne := SimpleGraph.connected_iff_ediam_ne_top.mp hconn obtain ⟨w, hw⟩ := hconn.exists_walk_length_eq_dist α5 β5 have h31 : 31 ≤ (simple_graph_reconfiguration_graph G5 (8 + 2)).diam := ((walk_len w).trans hw.le).trans (SimpleGraph.dist_le_diam hne) have hcard : Fintype.card (Fin 5 × Fin 5) = 25 := by simp rw [hcard] calc ((25 : ℕ) : ℕ∞) + graph_matching_num G5 ≤ 25 + 5 := add_le_add le_rfl G5_matching _ < 31 := by norm_num _ ≤ _ := by exact_mod_cast h31end Op1611LeEight/-- Theorem 4 of arXiv:2611.17022: an 8-regular graph certifying that the minimal maximum degree is at most 8. -/theorem op_1611_min_max_degree_le_eight : simple_graph_reconfiguration_diam_gt_matching 8 := by exact Op1611LeEight.le_eight_aux