AFTD Auto-Formalizing Theoretical Domains

maxcut_utility_add_monochromatic_card

theoremverified

A player's utility plus the number of its neighbours sharing its colour equals its degree.

Statement

theorem maxcut_utility_add_monochromatic_card {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (v : V) : maxcut_utility G σ v + (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 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)…
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
Used by 16

The proof, explained

The proof partitions the neighbours of a vertex v into two disjoint sets: those assigned a different colour from v, and those assigned the same colour as v. The number of neighbours with a differing colour is, by definition, the vertex's utility in the max-cut game, while the remaining neighbours are its monochromatic neighbours. Since the two groups partition the entire neighbourhood, their sizes sum to the degree of v.

  1. The degree of v is rewritten as the cardinality of its neighbourhood {w | G.Adj v w}.

    Enabling classical reasoning, we replace the degree of v with the cardinality of its neighbour finset using SimpleGraph.card_neighborFinset_eq_degree, and then express that neighbour finset as the subfinset of vertices adjacent to v using SimpleGraph.neighborFinset_eq_filter.

    lines 3–4

    uses SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter

      classical
      rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]
  2. The neighbours of v are partitioned into those with a different colour and those with the same colour.

    Applying card_filter_add_card_filter_not to the neighbour set of v with the predicate fun w => σ w ≠ σ v establishes that the number of neighbours with a different colour plus the number of neighbours without a different colour equals the total degree (neighbourhood size).

    lines 5–6

    uses card_filter_add_card_filter_not

      have h := (Finset.univ.filter (G.Adj v)).card_filter_add_card_filter_not
        (fun w => σ w ≠ σ v)
  3. The utility of v plus the count of monochromatic neighbours equals the degree of v.

    Simplifying the partitioned sum with Finset.filter_filter combines the nested filters into conjunctions with adjacency. By not_not, the condition ¬(σ w ≠ σ v) simplifies to σ w = σ v (monochromatic neighbours). By definition of maxcut_utility, the count of neighbours with differing colours is the utility of v, so the hypothesis matches the goal exactly.

    line 7

    uses Finset.filter_filter, not_not, maxcut_utility

      simpa only [Finset.filter_filter, not_not, maxcut_utility] using h
SimpleGraph.card_neighborFinset_eq_degree
The number of vertices in the neighbour finset of a vertex equals its degree.
SimpleGraph.neighborFinset_eq_filter
The neighbour finset of a vertex v consists of all vertices adjacent to v.
card_filter_add_card_filter_not
For any finite set s and predicate p, the number of elements in s satisfying p plus the number of elements not satisfying p equals the total size of s.
Finset.filter_filter
Filtering a finite set by predicate p and then by predicate q is equivalent to filtering it once by the conjunction p ∧ q.
not_not
Double negation elimination: ¬¬P is equivalent to P.
maxcut_utility
The definition of max-cut utility for vertex v under coloring σ: the number of neighbours of v assigned a different colour from 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

/-- Utility plus monochromatic neighbour count equals degree. -/theorem maxcut_utility_add_monochromatic_card {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (v : V) : maxcut_utility G σ v + (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = G.degree v := by  classical  rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]  have h := (Finset.univ.filter (G.Adj v)).card_filter_add_card_filter_not    (fun w => σ w ≠ σ v)  simpa only [Finset.filter_filter, not_not, maxcut_utility] using h
See it in the graphDiscuss this resultChallenge it