maxcut_utility_le_degree
A player's utility in the Max-k-Cut game never exceeds its degree: the neighbours cut away by v form a subset of the neighbours of v.
Statement
theorem maxcut_utility_le_degree {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (v : V) : maxcut_utility G σ v ≤ G.degree v
- Source
- step towards maxcut_game_strong_equilibrium_exists
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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)…
- maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
- Used by 5
- maxcut_optimal_of_proper_coloringA proper k-colouring of a finite simple graph is a maximum k-cut of the Max-k-Cut game: it cuts every edge, so each player's utility…
- maxcut_optimal_strong_of_color_unusedIf σ is an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and some colour c is never used by σ, then σ is a…
- maxcut_strong_equilibrium_of_proper_coloringA proper k-colouring of a finite simple graph is a strong equilibrium of the Max-k-Cut game: every player already has utility equal to its…
- maxcut_strong_equilibrium_of_saturated_vertexA coloring of a finite graph is a strong equilibrium if its restriction after deleting a vertex is a strong equilibrium and every edge…
- maxcut_unused_color_or_safe_pivot_of_proper_coloringIf a finite graph admits a proper k-coloring and N has fewer than 2k vertices, there is a strong equilibrium with an unused color on N or…
The proof, explained
The utility of a vertex v in the Max-k-Cut game counts neighbours assigned a different colour from v. The degree of v is the sum of these cut neighbours and the monochromatic neighbours (those assigned the same colour as v). Since all counts are non-negative, the utility cannot exceed the degree.
The sum of the utility of v and the number of neighbours sharing the colour of v equals the degree of v.
We apply the lemma `maxcut_utility_add_monochromatic_card`, which partitions the set of neighbours of v into those with a different colour (counted by `maxcut_utility`) and those with the same colour.
uses
maxcut_utility_add_monochromatic_cardhave := maxcut_utility_add_monochromatic_card G σ vThe utility of v is at most the degree of v.
Since the number of monochromatic neighbours is a non-negative integer, the relation a + b = c with b ≥ 0 immediately implies a ≤ c by linear arithmetic (`omega`).
omega
maxcut_utility_add_monochromatic_card- The utility of a vertex v (the number of its neighbours assigned a different colour from v) plus the number of its neighbours assigned the same colour as v equals the degree of v.
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.
/-- The utility of v is at most the degree of v. -/theorem maxcut_utility_le_degree {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (v : V) : maxcut_utility G σ v ≤ G.degree v := by have := maxcut_utility_add_monochromatic_card G σ v omega