AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_not_strong_degree_66

theoremverifiedformalization

There is a finite simple graph of maximum degree at most 66 with an optimal coloring of the Max-3-Cut game that is not a strong equilibrium; hence Δ*(3) ≤ 65. (The graph G_3 of arXiv:2610.04948, Sec. 2, has 91 vertices and maximum degree 66, attained by the anchor vertices r_{3,1}.)

Statement

theorem maxcut_optimal_not_strong_degree_66 : ¬ maxcut_optimal_strong_up_to_degree 3 66
Formalizes
arXiv:2610.04948, Theorem 2 for k = 3, with the degree bound read off the construction G_3 of Sec. 2.1 (the paper does not state the degree); the upper-bound side of list entry OP-86, a question proposed here from Corollary 9 (the known bound Δ ≤ 2k − 1 of Carosi et al., which the paper recovers).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • maxcut_optimal_strong_up_to_degreeFor k and D: on every finite simple graph of maximum degree at most D, every optimal coloring of the Max-k-Cut game with k colors is a…
  • maxcut_anchor_three_graphThe 91-vertex graph G_3 of arXiv:2610.04948: a 16-vertex core A,B,C,D and three anchor classes of 25 vertices. Indices and colors are…
  • maxcut_anchor_three_initial_coloringThe initial coloring sigma of the paper graph G_3: A and D have color 0, B color 1, C color 2, and anchor class j has color j.
  • maxcut_anchor_three_stable_coloringThe paper’s displayed post-deviation coloring on G_3: A has color 2, B color 0, C and D color 1, and anchor class j has color j, using…
  • maxcut_anchor_three_initial_optimalThe displayed initial coloring sigma of the 91-vertex graph G_3 in arXiv:2610.04948 maximizes social welfare among all three-colorings.
  • 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…
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.

The proof, explained

The theorem is proved by contradiction using an explicit counterexample graph G on 91 vertices (16 core vertices and 75 anchor vertices) equipped with an optimal 3-coloring. First, the maximum degree of G is bounded by 66: each core vertex has degree at most 66 by finite evaluation, and each anchor vertex connects to exactly 50 other anchor vertices and at most 16 core vertices. Second, an alternative coloring is shown by finite evaluation to be a beneficial coalition deviation for the 16 core vertices, where each strictly increases its utility while anchor colors stay unchanged. Consequently, this optimal coloring is not a strong equilibrium, showing that maximum degree 66 does not guarantee strong equilibrium for optimal colorings.

  1. Adjacency in the graph G is decidable.

    Unfolding the definitions of G and maxcut_anchor_three_graph reveals that adjacency is defined via the underlying relation, which Lean's typeclass synthesis infers to be decidable.

    lines 5–7

    private instance graph_decidable : DecidableRel G.Adj := by
      unfold G maxcut_anchor_three_graph
      infer_instance
  2. Two anchor vertices are adjacent in G if and only if their partition indices differ.

    By definition, two anchor vertices (j, i) and (l, t) are adjacent when they are distinct and j ≠ l ∨ l ≠ j. The forward direction follows immediately since either disjunct implies j ≠ l. Conversely, if j ≠ l, the vertices must be distinct (as equality would force j = l by projecting to the first coordinate via Prod.fst and Sum.inr.inj), establishing adjacency.

    lines 11–21

    uses Or.inl, congrArg, Prod.fst, Sum.inr.inj

    private lemma anchor_adj (j l : Fin 3) (i t : Fin 25) :
        G.Adj (.inr (j,i)) (.inr (l,t)) ↔ j ≠ l := by
      change ((Sum.inr (j,i) : V) ≠ Sum.inr (l,t) ∧ (j ≠ l ∨ l ≠ j)) ↔ j ≠ l
      constructor
      · rintro ⟨_, h | h⟩
        · exact h
        · exact h.symm
      · intro h
        refine ⟨?_, Or.inl h⟩
        intro heq
        exact h (congrArg Prod.fst (Sum.inr.inj heq))
  3. Every core vertex has degree at most 66 in G, establishing the degree bound in the core case.

    The degree bound deg(u) ≤ 66 is verified for each of the 16 core vertices by exhaustive evaluation (`decide`). For an arbitrary vertex v, splitting on whether v is a core vertex (Sum.inl u) or an anchor vertex (Sum.inr a) immediately dispatches the core vertex case.

    lines 22–26

    private lemma degree_bound : ∀ v, G.degree v ≤ 66 := by
      have hcore : ∀ u : Fin 16, G.degree (Sum.inl u) ≤ 66 := by decide
      intro v
      cases v with
      | inl u => exact hcore u
  4. An anchor vertex has exactly 50 neighbors among the anchor vertices.

    The degree of an anchor vertex (j, i) is rewritten as the sum of indicator functions over the vertex type, split via Fintype.sum_sum_type into sums over core and anchor vertices. Applying Fintype.sum_prod_type and rewriting adjacency via anchor_adj reduces the anchor-anchor neighbor count to an iterated sum over x ∈ Fin 3 and y ∈ Fin 25 of (if j ≠ x then 1 else 0). Case analysis on j ∈ {0, 1, 2} evaluates this sum to 50 in every case.

    lines 27–35

    uses SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter, Finset.card_filter, Fintype.sum_sum_type, Fintype.sum_prod_type, anchor_adj

      | inr a =>
        rcases a with ⟨j,i⟩
        rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter,
          Finset.card_filter, Fintype.sum_sum_type]
        have ha : (∑ w : Fin 3 × Fin 25,
            if G.Adj (.inr (j,i)) (.inr w) then 1 else 0) = 50 := by
          rw [Fintype.sum_prod_type]
          simp_rw [anchor_adj]
          fin_cases j <;> decide
  5. An anchor vertex has at most 16 neighbors among the core vertices.

    The number of core neighbors of an anchor vertex is a sum over the 16 core vertices of an indicator taking value 0 or 1. Bounding each term by 1 via Finset.sum_le_sum shows that this sum is at most 16.

    lines 36–40

    uses Finset.sum_le_sum

        have hb : (∑ u : Fin 16,
            if G.Adj (.inr (j,i)) (.inl u) then 1 else 0) ≤ 16 := by
          calc
            _ ≤ ∑ _u : Fin 16, 1 := Finset.sum_le_sum (fun u _ => by split_ifs <;> omega)
            _ = 16 := by decide
  6. Every anchor vertex has degree at most 66 in G, completing the proof that G has maximum degree at most 66.

    Substituting the exact value of 50 anchor neighbors into the total degree formula, linear arithmetic (`omega`) combines this with the bound of at most 16 core neighbors to conclude that the total degree is at most 16 + 50 = 66.

    lines 41–42

        rw [ha]
        omega
  7. The set of 16 core vertices forms a strict beneficial coalition deviation from the initial coloring to the stable coloring. automation

    A strong deviation requires that the deviating coalition is nonempty, all non-deviating vertices retain their colors, and every deviating vertex strictly increases its utility. Unfolding is_maxcut_strong_deviation, finite exhaustive evaluation (`decide`) confirms that all three conditions hold for the 16 core vertices.

    lines 44–49

    private lemma deviation : is_maxcut_strong_deviation G
        maxcut_anchor_three_initial_coloring
        (Finset.univ.filter fun v : V => v.isLeft)
        maxcut_anchor_three_stable_coloring := by
      unfold is_maxcut_strong_deviation
      decide
  8. Not every optimal 3-coloring in a graph of maximum degree at most 66 is a strong equilibrium.

    Assume for contradiction that every optimal 3-coloring in a graph of maximum degree at most 66 is a strong equilibrium. Applying this hypothesis to G, the degree bound of 66, the initial coloring, and its optimality (maxcut_anchor_three_initial_optimal) implies that the initial coloring must be a strong equilibrium. But MaxcutDegree66Check.deviation exhibits an explicit strong coalition deviation by the 16 core vertices, yielding a contradiction.

    lines 52–56

    uses MaxcutDegree66Check.degree_bound, maxcut_anchor_three_initial_optimal, MaxcutDegree66Check.deviation

    theorem maxcut_optimal_not_strong_degree_66 : ¬ maxcut_optimal_strong_up_to_degree 3 66 := by
      intro h
      have hs := h (Fin 16 ⊕ (Fin 3 × Fin 25)) maxcut_anchor_three_graph
        MaxcutDegree66Check.degree_bound maxcut_anchor_three_initial_coloring maxcut_anchor_three_initial_optimal
      exact hs _ _ MaxcutDegree66Check.deviation
Or.inl
Given a proof of P, produces a proof of the disjunction P ∨ Q.
congrArg
Equality is preserved under function application: if x = y, then f(x) = f(y).
Prod.fst
The first projection function mapping a pair (x, y) to x.
Sum.inr.inj
The right injection of a disjoint sum is injective: Sum.inr x = Sum.inr y implies x = y.
SimpleGraph.card_neighborFinset_eq_degree
The degree of a vertex in a simple graph equals the number of elements in its neighbor finset.
SimpleGraph.neighborFinset_eq_filter
The neighbor finset of a vertex v consists of all vertices w adjacent to v.
Finset.card_filter
The number of elements in a finite set satisfying a predicate equals the sum of the indicator function of that predicate over the set.
Fintype.sum_sum_type
A sum over a disjoint sum type α ⊕ β splits into the sum over α plus the sum over β.
Fintype.sum_prod_type
A sum over a product type α × β can be written as an iterated sum over α and then β.
anchor_adj
Two anchor vertices (j, i) and (l, t) are adjacent in G if and only if their color indices differ (j ≠ l).
Finset.sum_le_sum
If f(x) ≤ g(x) for all x in a finite set, then the sum of f over that set is at most the sum of g.
MaxcutDegree66Check.degree_bound
Every vertex in the graph G has degree at most 66.
maxcut_anchor_three_initial_optimal
The initial 3-coloring of G achieves maximum welfare (total cut value) among all 3-colorings.
MaxcutDegree66Check.deviation
The coalition of 16 core vertices forms a valid strong deviation from the initial coloring to the stable coloring.

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

open scoped BigOperatorsnamespace MaxcutDegree66Checkprivate abbrev V := Fin 16 ⊕ (Fin 3 × Fin 25)private abbrev G := maxcut_anchor_three_graphprivate instance graph_decidable : DecidableRel G.Adj := by  unfold G maxcut_anchor_three_graph  infer_instanceset_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000private lemma anchor_adj (j l : Fin 3) (i t : Fin 25) :    G.Adj (.inr (j,i)) (.inr (l,t)) ↔ j ≠ l := by  change ((Sum.inr (j,i) : V) ≠ Sum.inr (l,t) ∧ (j ≠ l ∨ l ≠ j)) ↔ j ≠ l  constructor  · rintro ⟨_, h | h⟩    · exact h    · exact h.symm  · intro h    refine ⟨?_, Or.inl h⟩    intro heq    exact h (congrArg Prod.fst (Sum.inr.inj heq))private lemma degree_bound : ∀ v, G.degree v ≤ 66 := by  have hcore : ∀ u : Fin 16, G.degree (Sum.inl u) ≤ 66 := by decide  intro v  cases v with  | inl u => exact hcore u  | inr a =>    rcases a with ⟨j,i⟩    rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter,      Finset.card_filter, Fintype.sum_sum_type]    have ha : (∑ w : Fin 3 × Fin 25,        if G.Adj (.inr (j,i)) (.inr w) then 1 else 0) = 50 := by      rw [Fintype.sum_prod_type]      simp_rw [anchor_adj]      fin_cases j <;> decide    have hb : (∑ u : Fin 16,        if G.Adj (.inr (j,i)) (.inl u) then 1 else 0) ≤ 16 := by      calc        _ ≤ ∑ _u : Fin 16, 1 := Finset.sum_le_sum (fun u _ => by split_ifs <;> omega)        _ = 16 := by decide    rw [ha]    omegaprivate lemma deviation : is_maxcut_strong_deviation G    maxcut_anchor_three_initial_coloring    (Finset.univ.filter fun v : V => v.isLeft)    maxcut_anchor_three_stable_coloring := by  unfold is_maxcut_strong_deviation  decideend MaxcutDegree66Checktheorem maxcut_optimal_not_strong_degree_66 : ¬ maxcut_optimal_strong_up_to_degree 3 66 := by  intro h  have hs := h (Fin 16 ⊕ (Fin 3 × Fin 25)) maxcut_anchor_three_graph    MaxcutDegree66Check.degree_bound maxcut_anchor_three_initial_coloring maxcut_anchor_three_initial_optimal  exact hs _ _ MaxcutDegree66Check.deviation
See it in the graphDiscuss this resultChallenge it