AFTD Auto-Formalizing Theoretical Domains

maxcut_cycle71_return_steps

theoremverified

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.

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

    lines 6–7

    uses Nat.mod_lt

        let a : Fin 33 := ⟨i.val + 1, by omega⟩
        let b : Fin 33 := ⟨(i.val + 2) % 33, Nat.mod_lt _ (by decide)⟩
  2. 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.

    line 9

    uses SimpleGraph.fromRel

          (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3
  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.

    line 12

      intro i
  4. For 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.

    line 13

      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.

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

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