AFTD Auto-Formalizing Theoretical Domains

maxcut_unweighted_strong_deviation_cycle_exists

theoremverifiedoriginal

There is an unweighted simple graph on 46 vertices and an infinite sequence of three-color profiles that returns to its starting profile after five steps, such that every consecutive pair is a profitable deviation by exactly the players who change colors.

Statement

theorem maxcut_unweighted_strong_deviation_cycle_exists :
    ∃ (G : SimpleGraph (Fin 46)) (d : DecidableRel G.Adj) (f : ℕ → Fin 46 → Fin 3),
      f 5 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ G d 3 (f n)
        (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1))
Related work
arXiv:1810.09278, Proposition 2 gives a cycle for a weighted game; Section 7 discusses strong potential in unweighted games. Related existence question: arXiv:2610.04948, Section 4.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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.
  • maxcut_cycle46_deviationsEach successive pair of the five displayed colorings, including the transition from the fifth to the first, is a strong deviation on the…
  • maxcut_five_cycle_repeatsAny five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence…
  • 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…

Read back from the Lean

There exist a simple graph G on the vertex set Fin 46, a decidability instance d for G's adjacency relation, and a sequence of 3-colorings f : ℕ → Fin 46 → Fin 3 such that: 1. f 5 = f 0 (the coloring returns to the initial coloring at step 5), and 2. for all n : ℕ, the step from f n to f (n + 1) is a strong deviation of the set of changing vertices Sₙ = {v : Fin 46 | f (n + 1) v ≠ f n v}, meaning that: - Sₙ is non-empty (at least one vertex changes its color), - every vertex not in Sₙ keeps its color (tautological by definition of Sₙ), and - for every vertex v ∈ Sₙ, the Max-Cut utility of v strictly increases from f n to f (n + 1), where the utility of v under a coloring σ is the number of neighbors w of v such that σ w ≠ σ v.

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 is proved by exhibiting an explicit 46-vertex unweighted graph and lifting a verified 5-cycle of colorings to an infinite sequence. The adjacency relation on this graph is defined by explicit arithmetic on finite coordinates, which Lean verifies is decidable. The recurrence theorem `maxcut_five_cycle_repeats` is applied to this graph, the explicit 5-stage coloring schedule `maxcut_cycle46_coloring`, and the pre-verified deviations `maxcut_cycle46_deviations` to yield an infinite 5-periodic sequence of 3-colorings where every step is a max-cut strong deviation. Exhibiting this graph, its decidability instance, and the sequence concludes the proof.

  1. The adjacency relation of the 46-vertex graph `maxcut_cycle46_graph` is decidable. automation

    For arbitrary vertices $u, v \\in \\text{Fin } 46$, we introduce them and unfold the definitions of the graph and `SimpleGraph.fromRel`. The adjacency relation is an explicit boolean combination of inequalities and modular arithmetic on finite numbers, so Lean's typeclass synthesis (`infer_instance`) automatically decides whether an edge is present.

    lines 2–4

      intro u v
      unfold maxcut_cycle46_graph SimpleGraph.fromRel
      infer_instance
  2. There exists an unweighted 46-vertex graph, a decidability instance for its adjacency, and an infinite 5-periodic sequence of 3-colorings such that every consecutive step is a max-cut strong deviation.

    We apply `maxcut_five_cycle_repeats` to the concrete 46-vertex graph `maxcut_cycle46_graph`, the 5-stage coloring schedule `maxcut_cycle46_coloring`, and the pre-verified deviations `maxcut_cycle46_deviations`. This produces an infinite sequence of 3-colorings $f : \\mathbb{N} \\to \\text{Fin } 46 \\to \\text{Fin } 3$ satisfying $f(5) = f(0)$ such that each transition $f(n) \\to f(n+1)$ is a strong deviation by the deviating vertices. Providing `maxcut_cycle46_graph`, the decidability instance `cycle46_decidable`, and the sequence $f$ witnesses the existential claim.

    lines 10–11

    uses maxcut_five_cycle_repeats, maxcut_cycle46_deviations

      obtain ⟨f, hperiod, hsteps⟩ := maxcut_five_cycle_repeats maxcut_cycle46_graph maxcut_cycle46_coloring maxcut_cycle46_deviations
      exact ⟨maxcut_cycle46_graph, cycle46_decidable, f, hperiod, hsteps⟩
maxcut_five_cycle_repeats
If a finite graph with decidable adjacency admits a 5-step cycle of colorings where each transition is a max-cut strong deviation by the moving vertices, then there exists an infinite sequence of colorings returning to its start after 5 steps ($f(5) = f(0)$) such that every consecutive transition is a strong deviation.
maxcut_cycle46_deviations
For every index $i \\in \\text{Fin } 5$, transitioning from stage $i$ to stage $i + 1$ in the 5-stage coloring schedule on the 46-vertex graph is a max-cut strong deviation by the vertices that change color.

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

private instance cycle46_decidable : DecidableRel maxcut_cycle46_graph.Adj := by  intro u v  unfold maxcut_cycle46_graph SimpleGraph.fromRel  infer_instancetheorem maxcut_unweighted_strong_deviation_cycle_exists :    ∃ (G : SimpleGraph (Fin 46)) (d : DecidableRel G.Adj) (f : ℕ → Fin 46 → Fin 3),      f 5 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ G d 3 (f n)        (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) := by  obtain ⟨f, hperiod, hsteps⟩ := maxcut_five_cycle_repeats maxcut_cycle46_graph maxcut_cycle46_coloring maxcut_cycle46_deviations  exact ⟨maxcut_cycle46_graph, cycle46_decidable, f, hperiod, hsteps⟩
See it in the graphDiscuss this resultChallenge it