AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_top_three_rainbow

theoremverified

On the triangle with three colors, the rainbow coloring is optimal.

Statement

theorem maxcut_optimal_top_three_rainbow :
    is_maxcut_optimal (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 1, 2]
Source
sanity check of is_maxcut_optimal
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).

The proof, explained

The theorem asserts that the rainbow coloring ![0, 1, 2] is an optimal Max-Cut coloring for the complete graph on three vertices with three available colors. Expanding the definition of optimality reduces the claim to verifying that every 3-coloring of the three vertices achieves at most the welfare of this rainbow coloring. Because there are only 27 candidate colorings in total, the inequality is verified by exhaustive computation via `decide`.

  1. For every 3-coloring τ of the complete graph on 3 vertices, the Max-Cut welfare of τ is at most the welfare of the rainbow coloring ![0, 1, 2]. automation

    Unfolding the definition of `is_maxcut_optimal` expresses the optimality condition as a universal quantification over all functions τ : Fin 3 → Fin 3: each such coloring must yield Max-Cut welfare at most that of the rainbow coloring ![0, 1, 2]. Since the vertex set Fin 3 and the color set Fin 3 are finite, there are only 3³ = 27 such colorings, and each welfare value is a finite sum of edge counts. The `decide` tactic checks this universal statement by exhaustive finite computation.

    line 3

      unfold is_maxcut_optimal; decide

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

theorem maxcut_optimal_top_three_rainbow :    is_maxcut_optimal (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 1, 2] := by  unfold is_maxcut_optimal; decide
See it in the graphDiscuss this resultChallenge it