maxcut_optimal_top_three_rainbow
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`.
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.
unfold is_maxcut_optimal; decide
- The proof relies on `decide`, which closes the goal by exhaustive computational evaluation over all 27 possible colorings of the 3-vertex complete 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.
theorem maxcut_optimal_top_three_rainbow : is_maxcut_optimal (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 1, 2] := by unfold is_maxcut_optimal; decide