maxcut_cycle71_force_closed_core
theoremverified
Any nonempty set of core vertices closed under adjacent vertices whose initial color is the first vertex’s deviation color contains all 32 core vertices.
Statement
theorem maxcut_cycle71_force_closed_core (S : Finset (Fin 71))
(hne : S.Nonempty) (hcore : ∀ v ∈ S, v.val < 32)
(hclosed : ∀ v ∈ S, ∀ w : Fin 71, w.val < 32 →
maxcut_cycle71_graph.Adj v w → maxcut_cycle71_coloring 0 w = maxcut_cycle71_coloring 1 v → w ∈ S) :
∀ w : Fin 71, w.val < 32 → w ∈ S- Source
- The forced-neighbor dependency graph in the 71-vertex minimal-deviation construction; experiment 12450.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- maxcut_cycle71_graphThe explicit 71-vertex finite simple graph with four core blocks of eight and three anchor blocks of thirteen, with edges determined by…
- maxcut_cycle71_coloringFive displayed three-color profiles on the regular 71-vertex construction, with anchor colors fixed and four core blocks recolored in…
- maxcut_cycle71_fieldThe number of anchor neighbors of each fixed color assigned to each core block in the regular 71-vertex construction.
- Used by 1
- maxcut_cycle71_first_deviation_minimalThe 32 core vertices have a profitable deviation from the first displayed profile to the second, and no proper subcoalition can profitably…
The proof, explained
Proof sketch placeholder.
Step lemma 1
Verified by computation.
unfold maxcut_cycle71_graph maxcut_cycle71_field simp only [SimpleGraph.fromRel_adj] decide +kernel
Step lemma 2
Verified by kernel decision.
decide +kernelStep lemma 3
Modulo identity.
unfold mc71_walk; rw [Nat.mod_mod]
Step 4
One step in the walk stays in S.
have hstep : ∀ i : ℕ, mc71_walk i ∈ S → mc71_walk (i + 1) ∈ S := by intro i hi have h := mc71_walk_step ⟨i % 40, Nat.mod_lt _ (by norm_num)⟩ simp only at h have e1 : mc71_walk (i % 40) = mc71_walk i := mc71_walk_mod i have e2 : mc71_walk (i % 40 + 1) = mc71_walk (i + 1) := by rw [← mc71_walk_mod (i % 40 + 1), ← mc71_walk_mod (i + 1), Nat.add_mod, Nat.mod_mod, ← Nat.add_mod] rw [e1, e2] at h exact hclosed _ hi _ h.2.1 h.2.2.1 h.2.2.2
Step 5
Induction on walk length.
have hiter : ∀ i k : ℕ, mc71_walk i ∈ S → mc71_walk (i + k) ∈ S := by intro i k hi induction k with | zero => simpa using hi | succ k ih => exact hstep _ ih
Step 6
Reach any target core vertex.
obtain ⟨v, hv⟩ := hne obtain ⟨i, hi⟩ := mc71_walk_covers v (hcore v hv) intro w hw obtain ⟨j, hj⟩ := mc71_walk_covers w hw have h := hiter i.val (j.val + 40 - i.val) (hi ▸ hv) have e : i.val + (j.val + 40 - i.val) = j.val + 40 := by omega rw [e, ← mc71_walk_mod, Nat.add_mod_right, Nat.mod_eq_of_lt j.isLt, hj] at h exact h
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.
/-- A closed walk through the forcing relation that visits all 32 core vertices. -/def mc71_walk (i : ℕ) : Fin 71 := [8, 1, 17, 9, 2, 18, 10, 0, 16, 13, 3, 19, 11, 4, 20, 12, 5, 21, 10, 6, 22, 14, 7, 23, 15, 25, 10, 24, 11, 26, 8, 27, 8, 28, 8, 29, 8, 30, 8, 31].getD (i % 40) 0theorem mc71_walk_step : ∀ i : Fin 40, (mc71_walk i.val).val < 32 ∧ (mc71_walk (i.val + 1)).val < 32 ∧ maxcut_cycle71_graph.Adj (mc71_walk i.val) (mc71_walk (i.val + 1)) ∧ maxcut_cycle71_coloring 0 (mc71_walk (i.val + 1)) = maxcut_cycle71_coloring 1 (mc71_walk i.val) := by unfold maxcut_cycle71_graph maxcut_cycle71_field simp only [SimpleGraph.fromRel_adj] decide +kerneltheorem mc71_walk_covers : ∀ w : Fin 71, w.val < 32 → ∃ j : Fin 40, mc71_walk j.val = w := by decide +kerneltheorem mc71_walk_mod (i : ℕ) : mc71_walk (i % 40) = mc71_walk i := by unfold mc71_walk; rw [Nat.mod_mod]theorem maxcut_cycle71_force_closed_core (S : Finset (Fin 71)) (hne : S.Nonempty) (hcore : ∀ v ∈ S, v.val < 32) (hclosed : ∀ v ∈ S, ∀ w : Fin 71, w.val < 32 → maxcut_cycle71_graph.Adj v w → maxcut_cycle71_coloring 0 w = maxcut_cycle71_coloring 1 v → w ∈ S) : ∀ w : Fin 71, w.val < 32 → w ∈ S := by have hstep : ∀ i : ℕ, mc71_walk i ∈ S → mc71_walk (i + 1) ∈ S := by intro i hi have h := mc71_walk_step ⟨i % 40, Nat.mod_lt _ (by norm_num)⟩ simp only at h have e1 : mc71_walk (i % 40) = mc71_walk i := mc71_walk_mod i have e2 : mc71_walk (i % 40 + 1) = mc71_walk (i + 1) := by rw [← mc71_walk_mod (i % 40 + 1), ← mc71_walk_mod (i + 1), Nat.add_mod, Nat.mod_mod, ← Nat.add_mod] rw [e1, e2] at h exact hclosed _ hi _ h.2.1 h.2.2.1 h.2.2.2 have hiter : ∀ i k : ℕ, mc71_walk i ∈ S → mc71_walk (i + k) ∈ S := by intro i k hi induction k with | zero => simpa using hi | succ k ih => exact hstep _ ih obtain ⟨v, hv⟩ := hne obtain ⟨i, hi⟩ := mc71_walk_covers v (hcore v hv) intro w hw obtain ⟨j, hj⟩ := mc71_walk_covers w hw have h := hiter i.val (j.val + 40 - i.val) (hi ▸ hv) have e : i.val + (j.val + 40 - i.val) = j.val + 40 := by omega rw [e, ← mc71_walk_mod, Nat.add_mod_right, Nat.mod_eq_of_lt j.isLt, hj] at h exact h