AFTD Auto-Formalizing Theoretical Domains

maxcut_cycle46_deviations

theoremverified

Each successive pair of the five displayed colorings, including the transition from the fifth to the first, is a strong deviation on the 46-vertex graph, with coalition exactly the vertices whose colors change.

Statement

theorem maxcut_cycle46_deviations :
    ∀ i : Fin 5,
      @is_maxcut_strong_deviation _ _ maxcut_cycle46_graph
        (by unfold maxcut_cycle46_graph; infer_instance) 3
        (maxcut_cycle46_coloring i)
        (Finset.univ.filter fun v => maxcut_cycle46_coloring (i + 1) v ≠ maxcut_cycle46_coloring i v)
        (maxcut_cycle46_coloring (i + 1))
Source
Concrete finite certificate for maxcut_unweighted_strong_deviation_cycle_exists, found via experiments 12434, 12437 and 12438.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_cycle46_graphA 46-vertex finite simple unweighted graph for a five-step strong-deviation cycle: four core blocks of eight, and two fixed-color anchor…
  • maxcut_cycle46_coloringThe five successive three-color profiles of the 46-vertex example, with stage addition modulo five.
  • 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

The proof, explained

To prove that each of the five successive colorings forms a strong deviation on the 46-vertex graph, the proof considers each transition in the 5-cycle individually. For each of the five cases, expanding the definition of a strong deviation reduces the claim to finite checks: verifying that the changing set is nonempty, that outside vertices are unchanged, and that every changing vertex strictly increases its number of cut neighbors. Since all graphs, colorings, and sets are finite, these conditions are verified by direct finite computation.

  1. The adjacency relation on the 46-vertex graph is decidable.

    Unfolding the definition of the graph reveals that the adjacency relation is defined by a boolean combination of inequalities and modulo arithmetic on finite integer types, for which typeclass resolution synthesizes a decidability instance.

    line 8

            (by unfold maxcut_cycle46_graph; infer_instance) 3
  2. Fix an arbitrary stage index i in {0, 1, 2, 3, 4}.

    We introduce i into the context to consider each transition individually.

    line 12

      intro i
  3. For each of the five transitions, the coalition is nonempty, vertices outside it do not change color, and every vertex in the coalition strictly increases its cut utility. automation

    We perform case analysis over all five values of i. In each case, we expand the definition of a strong deviation into its three conditions. Since the graph has 46 vertices and all relations and utilities are finite combinatorial objects, each case evaluates by direct computation.

    line 13

      fin_cases i <;> unfold is_maxcut_strong_deviation <;> decide

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_cycle46_deviations :    ∀ i : Fin 5,      @is_maxcut_strong_deviation _ _ maxcut_cycle46_graph        (by unfold maxcut_cycle46_graph; infer_instance) 3        (maxcut_cycle46_coloring i)        (Finset.univ.filter fun v => maxcut_cycle46_coloring (i + 1) v ≠ maxcut_cycle46_coloring i v)        (maxcut_cycle46_coloring (i + 1)) := by  intro i  fin_cases i <;> unfold is_maxcut_strong_deviation <;> decide
See it in the graphDiscuss this resultChallenge it