maxcut_welfare_top_three_rainbow
On the triangle, the coloring with three distinct colors has social welfare 6 (all three edges cut, each counted twice).
Statement
theorem maxcut_welfare_top_three_rainbow :
maxcut_welfare (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 1, 2] = 6- Source
- sanity check of maxcut_welfare
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
The proof, explained
On the complete graph on 3 vertices (the triangle), assigning each vertex a distinct color gives a rainbow coloring where every edge connects vertices of different colors. Each of the three vertices is adjacent to two vertices of different colors, contributing 2 to its utility, so the total social welfare is 2 + 2 + 2 = 6. Because all domains are finite, Lean proves the claim by direct computation using the `decide` tactic.
The social welfare of the coloring ![0, 1, 2] on the triangle graph is 6. automation
Because the vertex set `Fin 3` is finite, the utility of each vertex—defined as the count of adjacent vertices with different colors—and the total welfare (the sum of utilities over all three vertices) can be evaluated by finite computation. For each vertex, both adjacent vertices have distinct colors, giving utility 2 per vertex, and the sum over the 3 vertices evaluates directly to 6. Lean's `decide` tactic verifies this arithmetic identity automatically.
maxcut_welfare (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 1, 2] = 6 := by decide
- The proof is carried out entirely by finite computation (`decide`), which evaluates the definitions of welfare and utility on the finite graph without symbolic intermediate steps.
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_welfare_top_three_rainbow : maxcut_welfare (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 1, 2] = 6 := by decide