AFTD Auto-Formalizing Theoretical Domains

maxcut_five_cycle_repeats

theoremverified

Any five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence returning to its start after five steps.

Statement

theorem maxcut_five_cycle_repeats {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ}
    (colors : Fin 5 → V → Fin k)
    (hcycle : ∀ i : Fin 5,
      is_maxcut_strong_deviation G (colors i)
        (Finset.univ.filter fun v => colors (i + 1) v ≠ colors i v)
        (colors (i + 1))) :
    ∃ f : ℕ → V → Fin k,
      f 5 = f 0 ∧ ∀ n, is_maxcut_strong_deviation G (f n)
        (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1))
Source
Finite-cycle assembly for maxcut_unweighted_strong_deviation_cycle_exists.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…
Used by 1

The proof, explained

The theorem extends a 5-step cycle of strong deviations into an infinite periodic sequence of strong deviations. The strategy is to wrap the natural number time index modulo 5, defining f(n) = colors(n % 5). Periodicity f(5) = f(0) holds definitionally, and the deviation condition at step n follows from the cycle hypothesis by showing that the index for n + 1 equals the successor of the index for n in Fin 5.

  1. Define the candidate periodic sequence f and reduce the existential claim to periodicity and step-by-step strong deviation.

    We define f(n) = colors(⟨n % 5, ...⟩), taking the time index n modulo 5 and using Nat.mod_lt to certify that n % 5 < 5. Proposing f as the existential witness splits the goal into two obligations: verifying periodicity f(5) = f(0), and showing that each step from f(n) to f(n + 1) is a strong deviation.

    lines 11–12

    uses Nat.mod_lt

      let f : ℕ → V → Fin k := fun n => colors ⟨n % 5, Nat.mod_lt _ (by decide)⟩
      refine ⟨f, ?_, ?_⟩
  2. The sequence returns to its initial coloring after 5 steps: f(5) = f(0).

    Since 5 % 5 = 0 = 0 % 5, both f(5) and f(0) evaluate definitionally to colors(⟨0, ...⟩), so the equality holds by reflexivity.

    line 13

      · rfl
  3. For any n ∈ ℕ, the index (n + 1) % 5 equals (n % 5) + 1 in Fin 5.

    To connect the step from f(n) to f(n + 1) with the cycle hypothesis, we show that ⟨(n + 1) % 5, ...⟩ = ⟨n % 5, ...⟩ + 1 in Fin 5. By Fin.ext, it suffices to check this for their underlying natural numbers. The right-hand side has value ((n % 5) + 1) % 5 by Fin.val_add, which simplifies to (n + 1) % 5 by Nat.add_mod.

    lines 14–18

    uses Nat.mod_lt, Fin.ext, Fin.val_add, Nat.add_mod

      · intro n
        have hn : (⟨(n + 1) % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) =
            (⟨n % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) + 1 := by
          apply Fin.ext
          simp [Fin.val_add, Nat.add_mod]
  4. For every step n, f(n + 1) is a strong deviation from f(n).

    We specialize the cycle hypothesis hcycle to the index i = ⟨n % 5, ...⟩ in Fin 5. By the definition of f and the equality hn, f(n) is colors(i) and f(n + 1) is colors(i + 1). Substituting these into the specialized hypothesis matches the goal exactly, completing the proof.

    line 19

    uses Nat.mod_lt

        simpa [f, hn] using hcycle ⟨n % 5, Nat.mod_lt _ (by decide)⟩
Nat.mod_lt
For any natural numbers x and y with y > 0, the remainder x % y is strictly less than y.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Fin.val_add
The natural number value of the sum a + b in Fin n equals (↑a + ↑b) % n.
Nat.add_mod
For any natural numbers a, b, and n, (a + b) % n = (a % n + b % n) % n.

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

theorem maxcut_five_cycle_repeats {V : Type} [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ}    (colors : Fin 5 → V → Fin k)    (hcycle : ∀ i : Fin 5,      is_maxcut_strong_deviation G (colors i)        (Finset.univ.filter fun v => colors (i + 1) v ≠ colors i v)        (colors (i + 1))) :    ∃ f : ℕ → V → Fin k,      f 5 = f 0 ∧ ∀ n, is_maxcut_strong_deviation G (f n)        (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) := by  let f : ℕ → V → Fin k := fun n => colors ⟨n % 5, Nat.mod_lt _ (by decide)⟩  refine ⟨f, ?_, ?_⟩  · rfl  · intro n    have hn : (⟨(n + 1) % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) =        (⟨n % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) + 1 := by      apply Fin.ext      simp [Fin.val_add, Nat.add_mod]    simpa [f, hn] using hcycle ⟨n % 5, Nat.mod_lt _ (by decide)⟩
See it in the graphDiscuss this resultChallenge it