AFTD Auto-Formalizing Theoretical Domains

maxcut_fair9_witness

theoremverified

A specified three-color profile on the nine-vertex graph has utility at least four for every vertex and admits no profitable singleton deviation.

Statement

theorem maxcut_fair9_witness :
    (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph (maxcut_fair9_colors 1 2 2 1 2 1 0 0) v) ∧
    (∀ v : Fin 9, ∀ q : Fin 3,
      ¬ is_maxcut_strong_deviation maxcut_fair9_graph (maxcut_fair9_colors 1 2 2 1 2 1 0 0) {v}
        (Function.update (maxcut_fair9_colors 1 2 2 1 2 1 0 0) v q))
Source
Related work: arXiv:2610.04948, Section 4, asks whether all unweighted Max-k-Cut games have a strong equilibrium; this finite obstruction to selecting a fair Nash equilibrium was discovered in experiment 12959 and independently checked in 12961, 12964 and 12973.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_fair9_graphThe explicit nine-vertex simple graph used to obstruct fair Nash selection.
  • maxcut_fair9_colorsThe nine-vertex three-color profile whose first color is zero and whose remaining colors are specified by eight arguments.
  • 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 2

The proof, explained

The theorem states that a specific 3-coloring of a 9-vertex graph achieves a utility of at least 4 for every vertex and is stable against any single-vertex deviation (a Nash equilibrium in a fair max-cut game). Because the vertex set and color set are finite, the utilities and deviation conditions are decidable predicates; the proof simply unfolds their definitions and delegates the exhaustive check of all vertices and possible color deviations to Lean's kernel via `decide +kernel`.

  1. The adjacency relation of maxcut_fair9_graph is decidable.

    Unfolding the graph definition and `SimpleGraph.fromRel` reduces adjacency to checking whether two vertices are distinct and whether the pair (or its reverse) belongs to a finite list of 25 pairs. Typeclass synthesis (`infer_instance`) automatically constructs the decision procedure for this finite relation.

    lines 4–6

    uses SimpleGraph.fromRel

    private instance : DecidableRel maxcut_fair9_graph.Adj := by
      unfold maxcut_fair9_graph SimpleGraph.fromRel
      infer_instance
  2. The claim is rewritten in terms of explicit finite set comprehensions and cardinalities.

    Unfolding `is_maxcut_strong_deviation` and `maxcut_utility` converts the conditions into explicit statements about cardinalities of filtered finite subsets of vertices.

    line 13

      unfold is_maxcut_strong_deviation maxcut_utility
  3. Every vertex has utility at least 4, and no vertex can strictly increase its utility by changing its color. automation

    Lean's kernel evaluates the decidable proposition by finite exhaustive verification (`decide +kernel`). It verifies that each of the 9 vertices has at least 4 incident cut edges, and checks all 9 × 3 = 27 possible single-vertex color updates to confirm that none strictly increases the vertex's cut utility.

    line 14

      decide +kernel
SimpleGraph.fromRel
Given a binary relation on a vertex type V, constructs the simple graph whose adjacency relation is the irreflexive symmetric closure of the relation.

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 200000private instance : DecidableRel maxcut_fair9_graph.Adj := by  unfold maxcut_fair9_graph SimpleGraph.fromRel  infer_instancetheorem maxcut_fair9_witness :    (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph (maxcut_fair9_colors 1 2 2 1 2 1 0 0) v) ∧    (∀ v : Fin 9, ∀ q : Fin 3,      ¬ is_maxcut_strong_deviation maxcut_fair9_graph (maxcut_fair9_colors 1 2 2 1 2 1 0 0) {v}        (Function.update (maxcut_fair9_colors 1 2 2 1 2 1 0 0) v q)) := by  unfold is_maxcut_strong_deviation maxcut_utility  decide +kernel
See it in the graphDiscuss this resultChallenge it