maxcut_utility_add_monochromatic_card
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
- maxcut_utility_of_proper_coloringIf σ is a proper k-colouring of a finite simple graph G, then each player v has Max-k-Cut utility equal to its degree: maxcut_utility G σ…
- maxcut_defect_two_deviation_welfare_nondecreasingA strong deviation cannot decrease the cut value when every member of the deviating coalition initially has at most two same-colored…
- maxcut_optimal_no_clique_deviationIn the unweighted Max-k-Cut game on a finite simple graph, no coalition that induces a clique has a strong deviation from a…
- maxcut_defect_two_equal_welfare_deviation_structureIf a strong deviation from coalition defect at most two preserves welfare, every deviator has defect two before and one after, every old…
- maxcut_defect_one_strong_deviation_mono_decreasesA strong deviation from a coloring with at most one same-colored neighbor per vertex cannot create a monochromatic edge and must remove at…
- maxcut_strong_equilibrium_of_ranked_neighborsA coloring is a strong equilibrium if, for every alternative color at each vertex, the earlier-ranked neighbors of that color number at…
- maxcut_one_double_defect_deviation_decreasesIf a coloring has monochromatic degree at most two with at most one vertex of degree two, every strong deviation stays in that class and…
- 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_deviation_degree_sum_geLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- maxcut_one_double_defect_new_edge_uniqueUnder a strong deviation from a profile with maximum defect two and at most one defect-two vertex, all newly monochromatic edges coincide…
- maxcut_pinned_twins_optimum_rigidityEvery welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of…
- maxcut_utility_le_degreeA 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.
- 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_deviation_internal_color_count_ltLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- 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…
- maxcut_anchor_three_initial_optimalThe displayed initial coloring sigma of the 91-vertex graph G_3 in arXiv:2610.04948 maximizes social welfare among all three-colorings.
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.
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.
uses
SimpleGraph.card_neighborFinset_eq_degree,SimpleGraph.neighborFinset_eq_filterclassical rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]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).
uses
card_filter_add_card_filter_nothave h := (Finset.univ.filter (G.Adj v)).card_filter_add_card_filter_not (fun w => σ w ≠ σ v)
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.
uses
Finset.filter_filter,not_not,maxcut_utilitysimpa 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.
- The proof invokes `classical` to provide decidability instances for graph adjacency and colour equality, enabling set filtering and double negation elimination without constructive constraints.
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.
/-- 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