maxcut_op89_residual_exists_negation
The residual case maxcut_op89_residual_exists of OP-89 is false: it is not true that every finite simple graph G with k ≥ 3, at least 2k+2 vertices, not k-colorable and with a vertex of degree at least 2k, has an optimal Max-k-Cut coloring that is a strong equilibrium.
Statement
theorem maxcut_op89_residual_exists_negation : ¬ ∀ {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ), 3 ≤ k → 2 * k + 2 ≤ Fintype.card V → ¬ G.Colorable k → (∃ v, 2 * k ≤ G.degree v) → maxcut_has_optimal_strong_equilibrium G k
- Related work
- arXiv:2610.04948, Section 4 (concluding remarks), Question 2 (OP-89): does every unweighted Max-k-Cut game admit an optimal coloring that is a strong equilibrium? Refutes the residual case maxcut_op89_residual_exists with the pinned twins graph, k = 3.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- maxcut_pinned_twins_optimum_rigidityEvery welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of…
- maxcut_pinned_twins_not_colorable_threeThe 182-vertex pinned twins graph maxcut_pinned_twins_graph is not 3-colorable.
- maxcut_pinned_twins_refutes_of_rigidityIf every optimum of the explicit pinned-twin graph is its displayed initial coloring up to a global color permutation, then this graph has…
- maxcut_pinned_twins_graphA candidate counterexample graph on 182 vertices. Replace each vertex of the paper graph G_3 by two independent twins, replace each old…
- maxcut_has_optimal_strong_equilibriumIn the unweighted Max-k-Cut game on a finite simple graph G with k colors, there exists an optimal coloring σ : V → Fin k that is also a…
Read back from the Lean
The theorem asserts the negation of the following universal claim:
For every finite type $V$, simple graph $G$ on $V$ with decidable adjacency, and natural number $k$, if:
1. $k \ge 3$,
2. $|V| \ge 2k + 2$,
3. $G$ is not $k$-colorable, and
4. there exists a vertex $v \in V$ such that $\deg(v) \ge 2k$,
then there exists an assignment $\sigma : V \to \text{Fin } k$ that is both:
- optimal (it maximizes total welfare $\sum_{u \in V} \text{maxcut\_utility } G\ \sigma\ u$ over all $\tau : V \to \text{Fin } k$), and
- a strong equilibrium (no nonempty subset $S \subseteq V$ can jointly deviate to an assignment $\tau$ that agrees with $\sigma$ outside $S$ such that every vertex in $S$ strictly increases its maxcut_utility).
In other words, it asserts that the conjecture/implication above does not hold universally (i.e., there exists a counterexample).
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 proof refutes the universal conjecture by exhibiting an explicit counterexample: the graph maxcut_pinned_twins_graph with k = 3. Assuming the conjecture holds, we instantiate it on this graph, verifying that it has 182 ≥ 8 vertices, is not 3-colorable, and contains a vertex of degree at least 6. This produces an optimal Max-3-Cut strong equilibrium on maxcut_pinned_twins_graph, which contradicts the known rigidity theorem showing no such coloring exists.
The adjacency relation of maxcut_pinned_twins_graph is decidable.
We unfold the definition of maxcut_pinned_twins_graph, which is constructed from a relation via SimpleGraph.fromRel, and synthesize the decidability of its adjacency relation via typeclass inference.
private instance maxcut_op89_residual_exists_negation_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instance
Assume for contradiction that the residual claim holds.
We introduce the hypothesis h asserting that every finite graph G with k ≥ 3, |V(G)| ≥ 2k + 2, not k-colorable, and with a vertex of degree at least 2k admits an optimal Max-k-Cut coloring that is a strong equilibrium.
intro hIt suffices to show that maxcut_pinned_twins_graph has an optimal Max-3-Cut coloring that is a strong equilibrium.
By maxcut_pinned_twins_refutes_of_rigidity applied to maxcut_pinned_twins_optimum_rigidity, the graph maxcut_pinned_twins_graph has no optimal Max-3-Cut coloring that is a strong equilibrium. Therefore, proving that it does have one derives False.
uses
maxcut_pinned_twins_refutes_of_rigidity,maxcut_pinned_twins_optimum_rigidityapply maxcut_pinned_twins_refutes_of_rigidity maxcut_pinned_twins_optimum_rigidityInstantiating the contradiction hypothesis on maxcut_pinned_twins_graph with k = 3 reduces the goal to checking vertex count and minimum degree.
We instantiate h with maxcut_pinned_twins_graph and k = 3. The inequality 3 ≤ 3 holds by reflexivity (le_rfl), and non-3-colorability is provided by maxcut_pinned_twins_not_colorable_three. We choose the vertex (Sum.inl 0, 0) as the witness for the degree condition, leaving two subgoals: verifying the vertex count condition and the vertex degree condition.
uses
le_rfl,maxcut_pinned_twins_not_colorable_threerefine h maxcut_pinned_twins_graph 3 le_rfl ?_ maxcut_pinned_twins_not_colorable_three ⟨(.inl 0, 0), ?_⟩The graph maxcut_pinned_twins_graph has at least 2(3) + 2 = 8 vertices.
The vertex type is ((Fin 16 ⊕ Fin 3 × Fin 25) × Fin 2). Expanding the cardinality using Fintype.card_prod, Fintype.card_sum, and Fintype.card_fin gives (16 + 3 * 25) * 2 = 182 vertices, which norm_num evaluates to satisfy 2 * 3 + 2 ≤ 182.
uses
Fintype.card_prod,Fintype.card_sum,Fintype.card_fin· norm_num [Fintype.card_prod, Fintype.card_sum, Fintype.card_fin]The vertex (Sum.inl 0, 0) has degree at least 2(3) = 6.
We rewrite the degree as the cardinality of the neighbor finset using SimpleGraph.card_neighborFinset_eq_degree and express the neighbor finset as a filter over adjacent vertices using SimpleGraph.neighborFinset_eq_filter. The resulting finite cardinality inequality is verified by direct computation using decide.
uses
SimpleGraph.card_neighborFinset_eq_degree,SimpleGraph.neighborFinset_eq_filter· rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter] decide
le_rfl- reflexivity of a preorder: a ≤ a
Fintype.card_prod- the cardinality of a Cartesian product is the product of the cardinalities
Fintype.card_sum- the cardinality of a disjoint sum is the sum of the cardinalities
Fintype.card_fin- the cardinality of Fin n is n
SimpleGraph.card_neighborFinset_eq_degree- the degree of a vertex in a simple graph equals the cardinality of its neighbor finset
SimpleGraph.neighborFinset_eq_filter- the neighbor finset of a vertex consists of all vertices adjacent to it
maxcut_pinned_twins_refutes_of_rigidity- rigidity of optimal colorings refutes the existence of an optimal Max-3-Cut strong equilibrium on maxcut_pinned_twins_graph
maxcut_pinned_twins_optimum_rigidity- every optimal Max-3-Cut coloring of maxcut_pinned_twins_graph is equal to the canonical anchor coloring up to a permutation of colors
maxcut_pinned_twins_not_colorable_three- maxcut_pinned_twins_graph is not 3-colorable
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.
private instance maxcut_op89_residual_exists_negation_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instancetheorem maxcut_op89_residual_exists_negation : ¬ ∀ {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ), 3 ≤ k → 2 * k + 2 ≤ Fintype.card V → ¬ G.Colorable k → (∃ v, 2 * k ≤ G.degree v) → maxcut_has_optimal_strong_equilibrium G k := by intro h apply maxcut_pinned_twins_refutes_of_rigidity maxcut_pinned_twins_optimum_rigidity refine h maxcut_pinned_twins_graph 3 le_rfl ?_ maxcut_pinned_twins_not_colorable_three ⟨(.inl 0, 0), ?_⟩ · norm_num [Fintype.card_prod, Fintype.card_sum, Fintype.card_fin] · rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter] decide