AFTD Auto-Formalizing Theoretical Domains

maxcut_utility_le_degree

theoremverified

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

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.

  1. 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.

    line 3

    uses maxcut_utility_add_monochromatic_card

      have := maxcut_utility_add_monochromatic_card G σ v
  2. The 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`).

    line 4

      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

/-- 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
See it in the graphDiscuss this resultChallenge it