AFTD Auto-Formalizing Theoretical Domains

maxcut_three_leaf_star_no_fixed_profile_extension

theoremverified

The identity three-coloring is a strong equilibrium on three isolated vertices, but restoring a new center adjacent to all three cannot extend that same profile to a strong equilibrium using any of the three colors.

Statement

theorem maxcut_three_leaf_star_no_fixed_profile_extension :
    is_maxcut_strong_equilibrium (⊥ : SimpleGraph (Fin 3)) (id : Fin 3 → Fin 3) ∧
    ∀ c : Fin 3, ¬ is_maxcut_strong_equilibrium maxcut_three_leaf_star_graph (Fin.cases c id)
Source
Finite obstruction computed in experiment 16369.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_three_leaf_star_graphThe three-leaf star, with vertex zero at the center.
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
  • maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
  • 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…

Lean source view module on GitHub

set_option maxRecDepth 100000
set_option maxHeartbeats 12000000
instance : DecidableRel maxcut_three_leaf_star_graph.Adj := by
  unfold maxcut_three_leaf_star_graph
  infer_instance

theorem maxcut_three_leaf_star_no_fixed_profile_extension :
    is_maxcut_strong_equilibrium (⊥ : SimpleGraph (Fin 3)) (id : Fin 3 → Fin 3) ∧
    ∀ c : Fin 3, ¬ is_maxcut_strong_equilibrium maxcut_three_leaf_star_graph (Fin.cases c id) := by
  unfold is_maxcut_strong_equilibrium is_maxcut_strong_deviation maxcut_utility
  decide
See it in the graphDiscuss this resultChallenge it