maxcut_cycle71_return_steps
Every one of the 32 successive restoration moves, including the wraparound, is a profitable deviation by the displayed single vertex and changes no other vertex.
Statement
theorem maxcut_cycle71_return_steps : ∀ i : Fin 32, let a : Fin 33 := ⟨i.val + 1, by omega⟩ let b : Fin 33 := ⟨(i.val + 2) % 33, Nat.mod_lt _ (by decide)⟩ @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3 (maxcut_cycle71_return_stages a) {maxcut_cycle71_return_vertex i} (maxcut_cycle71_return_stages b) ∧ Finset.univ.filter (fun v : Fin 71 => maxcut_cycle71_return_stages b v ≠ maxcut_cycle71_return_stages a v) = {maxcut_cycle71_return_vertex i}
- Source
- The explicit 71-vertex unweighted minimal-deviation cycle for the potential-function question in arXiv:1810.09278, Section 7; experiments 12443, 12444, 12450 and 12452.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_fieldThe number of anchor neighbors of each fixed color assigned to each core block in the regular 71-vertex construction.
- maxcut_cycle71_return_vertexThe core vertex restored at each of the 32 singleton stages.
- maxcut_cycle71_return_stagesThe 33 profiles of the displayed 71-vertex cycle: the initial profile, the joint deviation, and the partial singleton restorations.
- is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
- maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
- Used by 1
- maxcut_cycle71_minimal_cycle_stepsEvery successive pair of the 33 profiles forms a strong deviation, and no proper subcoalition of its changing vertices has a profitable…
The proof, explained
The theorem states that each of the 32 successive restoration steps along the return cycle—including the final wraparound transition from stage 32 to stage 0—is a profitable strong deviation by a single specified vertex, leaving all other vertices unchanged. The proof proceeds by an exhaustive case analysis over all 32 values of the step index i ∈ {0, ..., 31} using fin_cases. For each case, the definitions of strong deviation and cut utility are unfolded, reducing the assertion to explicit cut size comparisons on a 71-vertex graph. Lean's kernel decision procedure (decide +kernel) then computes each cut and confirms both the strict increase in utility and the uniqueness of the deviating vertex.
The stage index a = i + 1 and the next stage index b = (i + 2) mod 33 are well-defined elements of Fin 33. automation
For any i < 32, linear integer arithmetic (omega) confirms that i + 1 < 33. For the wraparound stage index, 0 < 33 is verified by decide, which by Nat.mod_lt ensures that (i + 2) % 33 < 33.
uses
Nat.mod_ltlet a : Fin 33 := ⟨i.val + 1, by omega⟩ let b : Fin 33 := ⟨(i.val + 2) % 33, Nat.mod_lt _ (by decide)⟩
The adjacency relation of maxcut_cycle71_graph is decidable. automation
By introducing two vertices u and v and unfolding the definitions of maxcut_cycle71_graph, its coordinate field maxcut_cycle71_field, and SimpleGraph.fromRel, the adjacency condition is expressed in terms of decidable inequalities and modular arithmetic on finite coordinates. Typeclass inference (infer_instance) synthesizes the required decidability instance.
uses
SimpleGraph.fromRel(by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3
Fix an arbitrary restoration step index i ∈ {0, ..., 31}.
We introduce the step index i, representing one of the 32 restoration steps whose deviation properties need to be verified.
intro iFor every step index i ∈ {0, ..., 31}, the transition from stage a to stage b is a strong deviation by vertex maxcut_cycle71_return_vertex i, and no other vertex changes color. automation
We perform an exhaustive case analysis across all 32 values of i using fin_cases. In each case, unfolding is_maxcut_strong_deviation and maxcut_utility expands the definitions into concrete cut evaluations and neighbor counts. Lean's kernel evaluator (decide +kernel) checks each of the 32 cases directly, confirming that the specified vertex strictly increases its cut utility and that the set of vertices changing color is precisely the singleton containing that vertex.
fin_cases i <;> unfold is_maxcut_strong_deviation maxcut_utility <;> decide +kernel
Nat.mod_lt- For any natural numbers x and y, if 0 < y, then x % y < y.
SimpleGraph.fromRel- Constructs a simple graph from a binary relation by removing self-loops and taking the symmetric closure.
- The entire combinatorial verification across all 32 cases is performed by kernel evaluation (decide +kernel), which computes graph cuts, neighborhood cardinalities, and color comparisons directly without producing human-readable intermediate steps.
- The tactic blocks in lines 6, 7, and 9 occur within the theorem statement itself to discharge Lean's typechecking obligations: ensuring that the stage indices belong to Fin 33 and synthesizing an explicit DecidableRel instance for graph adjacency.
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.
set_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000theorem maxcut_cycle71_return_steps : ∀ i : Fin 32, let a : Fin 33 := ⟨i.val + 1, by omega⟩ let b : Fin 33 := ⟨(i.val + 2) % 33, Nat.mod_lt _ (by decide)⟩ @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3 (maxcut_cycle71_return_stages a) {maxcut_cycle71_return_vertex i} (maxcut_cycle71_return_stages b) ∧ Finset.univ.filter (fun v : Fin 71 => maxcut_cycle71_return_stages b v ≠ maxcut_cycle71_return_stages a v) = {maxcut_cycle71_return_vertex i} := by intro i fin_cases i <;> unfold is_maxcut_strong_deviation maxcut_utility <;> decide +kernel