AFTD Auto-Formalizing Theoretical Domains

op_1611_min_max_degree_le_eight

theoremverifiedformalization

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

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

    lines 7–12

    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⟩
    
  2. 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.

    lines 17–24

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

    lines 25–40

    uses graph_matching_num_le_vertex_cover_num, Set.encard_coe_eq_coe_finsetCard

    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
    
  4. α₅ 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.

    lines 41–53

    /-- 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)
    
  5. β₅ 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.

    lines 54–66

    /-- 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)
    
  6. α₅ and β₅ disagree at every vertex of G₅. automation

    Kernel evaluation checks all 25 vertices to confirm that α₅(p) ≠ β₅(p) for every vertex p.

    lines 67–68

    theorem α5_ne_β5 : ∀ p, α5 p ≠ β5 p := by decide +kernel
    
  7. 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).

    lines 76–97

    uses steps_unique, Finset.card_biUnion, Finset.card_le_card

    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).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)
    
  8. 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.

    lines 98–122

    uses Nat.le_induction, getVert_const

    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 this
    
  9. 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).

    lines 123–165

    uses steps_one, steps_two, getVert_const

    theorem 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)
    
  10. 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.

    lines 183–186

    uses steps_unique

    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)
    
  11. 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.

    lines 187–206

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

    lines 207–251

    uses claim1_aux, steps_two, steps_one

    theorem 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
  13. 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.

    lines 256–323

    uses bonus_sum, count_key, count

    theorem 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
    
  14. 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).

    lines 327–450

    uses exists_free_colour, reach_update, clear_nbrs, reach_beta, recolour_connected

    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
      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
  15. 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).

    lines 452–468

    uses claim2, claim1, count, sum_steps_le

    theorem 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)
    
  16. 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₅).

    lines 469–486

    uses G5_maxDegree, recolour_connected, walk_len, SimpleGraph.dist_le_diam, G5_matching

    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 h31
    
    end Op1611LeEight
    
  17. 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.

    lines 488–490

    uses Op1611LeEight.le_eight_aux

    theorem 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₅.

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

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