maxcut_strong_deviation_top_three_constant
On the triangle with three colors, from the constant coloring the coalition of two vertices that recolor to the two other colors is a strong deviation.
Statement
theorem maxcut_strong_deviation_top_three_constant :
is_maxcut_strong_deviation (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 0, 0] {1, 2} ![0, 1, 2]- Source
- sanity check of is_maxcut_strong_deviation
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
- Used by 1
- maxcut_not_strong_equilibrium_top_three_constantOn the triangle with three colors, the constant coloring is not a strong equilibrium.
The proof, explained
In the complete graph on three vertices with three colors, starting from the monochromatic coloring where every vertex has color 0, the coalition {1, 2} can recolor to colors 1 and 2 respectively. Unfolding the definition of a strong deviation yields three finite conditions: the coalition is nonempty, the remaining vertex 0 does not change color, and both vertices in the coalition strictly increase their cut utility from 0 to 2. The `decide` tactic verifies these decidable conditions by finite evaluation.
The coalition {1, 2} switching from the constant coloring (0, 0, 0) to (0, 1, 2) is a strong deviation on K₃ with 3 colors.
Unfolding `is_maxcut_strong_deviation` reduces the claim to three conditions: {1, 2} is nonempty; the color of every vertex outside {1, 2} (only vertex 0) remains unchanged, which holds since both colorings assign 0 to vertex 0; and each vertex in {1, 2} strictly increases its cut utility. In K₃ with the constant coloring (0, 0, 0), no edge is cut, so every vertex has cut utility 0. In the coloring (0, 1, 2), all three vertices have pairwise distinct colors, so every vertex has cut utility 2 (both incident edges are cut). Since 0 < 2, both coalition members strictly improve their utility. Because the graph and colorings are finite, the `decide` tactic checks these conditions by direct computation.
unfold is_maxcut_strong_deviation; 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
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_strong_deviation_top_three_constant : is_maxcut_strong_deviation (⊤ : SimpleGraph (Fin 3)) (k := 3) ![0, 0, 0] {1, 2} ![0, 1, 2] := by unfold is_maxcut_strong_deviation; decide