maxcut_fair9_witness
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
- maxcut_fair9_nash_fairness_obstructionOn the specified nine-vertex three-color graph there is a singleton-stable profile with every utility at least four, no strong equilibrium…
- maxcut_fair9_no_maxmin_strong_nashOn the specified nine-vertex graph, no strong equilibrium has minimum utility at least that of every singleton-stable three-coloring.
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`.
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.
uses
SimpleGraph.fromRelprivate instance : DecidableRel maxcut_fair9_graph.Adj := by unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instance
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.
unfold is_maxcut_strong_deviation maxcut_utilityEvery 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.
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.
- The proof relies entirely on Lean's kernel computation (`decide +kernel`) to exhaustively check all vertices and deviation profiles on a finite 9-vertex graph.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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