AFTD Auto-Formalizing Theoretical Domains

maxcut_op89_residual_exists_negation

theoremverifiedoriginal

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

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.

  1. 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.

    lines 1–4

    private instance maxcut_op89_residual_exists_negation_dec :
        DecidableRel maxcut_pinned_twins_graph.Adj := by
      unfold maxcut_pinned_twins_graph
      infer_instance
  2. 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.

    line 10

      intro h
  3. It 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.

    line 11

    uses maxcut_pinned_twins_refutes_of_rigidity, maxcut_pinned_twins_optimum_rigidity

      apply maxcut_pinned_twins_refutes_of_rigidity maxcut_pinned_twins_optimum_rigidity
  4. Instantiating 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.

    lines 12–13

    uses le_rfl, maxcut_pinned_twins_not_colorable_three

      refine h maxcut_pinned_twins_graph 3 le_rfl ?_ maxcut_pinned_twins_not_colorable_three
        ⟨(.inl 0, 0), ?_⟩
  5. 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.

    line 14

    uses Fintype.card_prod, Fintype.card_sum, Fintype.card_fin

      · norm_num [Fintype.card_prod, Fintype.card_sum, Fintype.card_fin]
  6. 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.

    lines 15–16

    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

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
See it in the graphDiscuss this resultChallenge it