AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_of_saturated_vertex

theoremverified

A coloring of a finite graph is a strong equilibrium if its restriction after deleting a vertex is a strong equilibrium and every edge incident to the deleted vertex is cut by the coloring.

Statement

theorem maxcut_strong_equilibrium_of_saturated_vertex
    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (v : V) {k : ℕ} (σ : V → Fin k)
    (hproper : ∀ w, G.Adj v w → σ w ≠ σ v)
    (hsub : is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V))
      (fun x => σ x.1)) :
    is_maxcut_strong_equilibrium G σ
Source
Structural reduction for OP-85, the unweighted Max-k-Cut strong-equilibrium existence problem in arXiv:2610.04948, Section 4.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • maxcut_single_vertex_sum_strong_equilibriumIf a finite graph is covered by two induced subgraphs meeting in one vertex with no edge between their exclusive parts, and a coloring…
  • 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_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
  • 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…
  • 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)…
Used by 1

The proof, explained

The theorem is proved by contradiction: suppose a coalition S has a profitable strong deviation τ in G. Because every edge incident to v is cut under σ, v already achieves its maximum possible cut utility (its degree) and therefore cannot belong to S. Restricting the coalition to the remaining vertices A = V \ {v} yields a nonempty coalition S' on G[A]. Decomposing the cut utility of each vertex in A into its internal edges in G[A] and its edge to v shows that the edge to v contributes at least as much to the utility under σ as under τ, so every vertex in S' must also strictly improve its utility within G[A], contradicting the assumption that the restricted coloring is a strong equilibrium.

  1. Define the set A of all vertices other than v.

    We work classically and define the finite set A = V \ {v}, which corresponds to the vertex set of the induced subgraph after deleting v.

    lines 10–11

      classical
      let A : Finset V := Finset.univ.erase v
  2. Under the coloring σ, vertex v achieves the maximum possible cut utility, equal to its degree.

    By the hypothesis hproper, every neighbor of v receives a color distinct from σ(v), so the set of neighbors sharing v's color is empty (Finset.filter_eq_empty_iff.mpr). Since cut utility plus the number of monochromatic neighbors equals the vertex degree (maxcut_utility_add_monochromatic_card), v's cut utility under σ is exactly deg(v).

    lines 12–18

    uses Finset.filter_eq_empty_iff.mpr, maxcut_utility_add_monochromatic_card

      have hfull : maxcut_utility G σ v = G.degree v := by
        have hz : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v) = ∅ := by
          apply Finset.filter_eq_empty_iff.mpr
          intro w _ ⟨hw, heq⟩
          exact hproper w hw heq
        have h := maxcut_utility_add_monochromatic_card G σ v
        simpa [hz] using h
  3. For any coloring p and any vertex x ∈ A, the cut utility of x in G decomposes into its cut utility in G[A] plus an indicator for the edge between x and v.

    For a vertex x ∈ A, let P(w) be the condition that w is adjacent to x and p(w) ≠ p(x). Since the vertex set of G partitions into A and {v} with v ∉ A, the neighbors of x satisfying P partition into those in A and, if P(v) holds, the vertex v itself (Finset.filter_insert). Rewriting the count over A as the cut utility in the induced subgraph G[A] via the subtype cardinality equivalence maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype yields the decomposition.

    lines 19–33

    uses Finset.filter_insert, maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype

      have hsplit : ∀ (p : V → Fin k) (x : V) (hx : x ∈ A),
          maxcut_utility G p x =
            maxcut_utility (G.induce (↑A : Set V)) (fun y => p y.1) ⟨x,hx⟩ +
              if G.Adj x v ∧ p v ≠ p x then 1 else 0 := by
        intro p x hx
        let P : V → Prop := fun w => G.Adj x w ∧ p w ≠ p x
        have hcard : (Finset.univ.filter P).card = (A.filter P).card + if P v then 1 else 0 := by
          have huniv : insert v A = Finset.univ := by simp [A]
          have hnot : v ∉ A.filter P := by simp [A]
          rw [← huniv, Finset.filter_insert]
          by_cases hp : P v <;> simp [hp, hnot]
        have hsubcard := maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype A P
        change (Finset.univ.filter P).card = (Finset.univ.filter (fun y : (↑A : Set V) => P y.1)).card + if P v then 1 else 0
        rw [hsubcard]
        exact hcard
  4. No strong deviation (S, τ) from σ in G can contain the vertex v.

    Suppose for contradiction that (S, τ) is a strong deviation in G. If v were in S, then v would strictly improve its cut utility, giving u_G(τ, v) > u_G(σ, v) = deg(v). But a vertex's cut utility can never exceed its degree (maxcut_utility_le_degree), yielding an arithmetic contradiction via omega. Thus v ∉ S.

    lines 34–39

    uses maxcut_utility_le_degree

      intro S τ hdev
      have hvS : v ∉ S := by
        intro hv
        have hg := hdev.2.2 v hv
        have hu := maxcut_utility_le_degree G τ v
        omega
  5. The restriction of the deviating coalition S to A, denoted S', is nonempty.

    We define S' as the subset of A consisting of those vertices that belong to S. Since (S, τ) is a strong deviation, S is nonempty, so it contains some vertex x. Because v ∉ S, x ≠ v, so x ∈ A, which means S' is nonempty.

    lines 40–45

      let S' : Finset (↑A : Set V) := Finset.univ.filter (fun x => x.1 ∈ S)
      have hdev' : is_maxcut_strong_deviation (G.induce (↑A : Set V)) (fun x => σ x.1) S' (fun x => τ x.1) := by
        refine ⟨?_, ?_, ?_⟩
        · obtain ⟨x, hx⟩ := hdev.1
          have hxne : x ≠ v := by intro h; subst x; exact hvS hx
          exact ⟨⟨x, by simp [A, hxne]⟩, by simp [S', hx]⟩
  6. Vertices outside S' retain their original colors under τ|_A.

    Any vertex x ∈ A not in S' does not belong to S. Because τ is a deviation on G, it leaves all vertices outside S unchanged, so τ(x) = σ(x).

    lines 46–48

        · intro x hx
          have hxS : x.1 ∉ S := by simpa [S'] using hx
          exact hdev.2.1 x.1 hxS
  7. Every vertex in S' strictly increases its cut utility in G[A] under τ|_A, establishing that (S', τ|_A) is a strong deviation in G[A].

    For any x ∈ S', we have x ∈ S, so x strictly improves its cut utility in G: u_G(σ, x) < u_G(τ, x). By the utility decomposition formula hsplit, this means u_{G[A]}(σ|_A, x) + 1_σ < u_{G[A]}(τ|_A, x) + 1_τ, where 1_p indicates whether the edge {x, v} is cut by p. If x is adjacent to v, then by symmetry of adjacency (G.adj_symm) and inequality symmetry (Ne.symm), the hypothesis that all edges incident to v are cut under σ guarantees σ(v) ≠ σ(x), making 1_σ = 1 while 1_τ ≤ 1 (simplified via true_and and if_true); if x is not adjacent to v, both indicators are 0. In either case 1_τ ≤ 1_σ, which implies u_{G[A]}(σ|_A, x) < u_{G[A]}(τ|_A, x).

    lines 49–60

    uses Ne.symm, G.adj_symm, true_and, if_true

        · rintro ⟨x, hxA⟩ hx
          have hxS : x ∈ S := by simpa [S'] using hx
          have hg := hdev.2.2 x hxS
          have ha : (if G.Adj x v ∧ τ v ≠ τ x then 1 else 0 : ℕ) ≤
              (if G.Adj x v ∧ σ v ≠ σ x then 1 else 0 : ℕ) := by
            by_cases hadj : G.Adj x v
            · have hp : σ v ≠ σ x := Ne.symm (hproper x (G.adj_symm hadj))
              simp only [hadj, hp, true_and, if_true]
              split <;> omega
            · simp [hadj]
          rw [hsplit σ x hxA, hsplit τ x hxA] at hg
          omega
  8. The existence of the strong deviation (S', τ|_A) contradicts the assumption that σ|_A is a strong equilibrium in G[A].

    Applying the hypothesis hsub (that the restriction of σ to G[A] is a strong equilibrium) to the deviation (S', τ|_A) produces False, which completes the proof that σ is a strong equilibrium in G.

    line 61

      exact hsub S' (fun x => τ x.1) hdev'
Finset.filter_eq_empty_iff.mpr
A filtered finite set is empty if no element satisfies the filtering predicate.
maxcut_utility_add_monochromatic_card
For any vertex in a simple graph, its cut utility plus the number of its monochromatic incident edges equals its degree.
Finset.filter_insert
Filtering an inserted element into a finite set adds the element if it satisfies the predicate, and leaves the filtered set unchanged otherwise.
maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype
The number of elements satisfying a predicate in a subtype of a finite set equals the cardinality of the filtered subset in the ambient set.
maxcut_utility_le_degree
The cut utility of any vertex under any coloring cannot exceed the degree of that vertex.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
G.adj_symm
Adjacency in a simple graph is symmetric: if x is adjacent to v, then v is adjacent to x.
true_and
The logical conjunction True ∧ p simplifies to p.
if_true
A conditional expression whose branch condition is True simplifies to its 'then' branch.

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

open Finsettheorem maxcut_strong_equilibrium_of_saturated_vertex    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (v : V) {k : ℕ} (σ : V → Fin k)    (hproper : ∀ w, G.Adj v w → σ w ≠ σ v)    (hsub : is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V))      (fun x => σ x.1)) :    is_maxcut_strong_equilibrium G σ := by  classical  let A : Finset V := Finset.univ.erase v  have hfull : maxcut_utility G σ v = G.degree v := by    have hz : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v) = ∅ := by      apply Finset.filter_eq_empty_iff.mpr      intro w _ ⟨hw, heq⟩      exact hproper w hw heq    have h := maxcut_utility_add_monochromatic_card G σ v    simpa [hz] using h  have hsplit : ∀ (p : V → Fin k) (x : V) (hx : x ∈ A),      maxcut_utility G p x =        maxcut_utility (G.induce (↑A : Set V)) (fun y => p y.1) ⟨x,hx⟩ +          if G.Adj x v ∧ p v ≠ p x then 1 else 0 := by    intro p x hx    let P : V → Prop := fun w => G.Adj x w ∧ p w ≠ p x    have hcard : (Finset.univ.filter P).card = (A.filter P).card + if P v then 1 else 0 := by      have huniv : insert v A = Finset.univ := by simp [A]      have hnot : v ∉ A.filter P := by simp [A]      rw [← huniv, Finset.filter_insert]      by_cases hp : P v <;> simp [hp, hnot]    have hsubcard := maxcut_single_vertex_sum_strong_equilibrium_card_filter_subtype A P    change (Finset.univ.filter P).card = (Finset.univ.filter (fun y : (↑A : Set V) => P y.1)).card + if P v then 1 else 0    rw [hsubcard]    exact hcard  intro S τ hdev  have hvS : v ∉ S := by    intro hv    have hg := hdev.2.2 v hv    have hu := maxcut_utility_le_degree G τ v    omega  let S' : Finset (↑A : Set V) := Finset.univ.filter (fun x => x.1 ∈ S)  have hdev' : is_maxcut_strong_deviation (G.induce (↑A : Set V)) (fun x => σ x.1) S' (fun x => τ x.1) := by    refine ⟨?_, ?_, ?_⟩    · obtain ⟨x, hx⟩ := hdev.1      have hxne : x ≠ v := by intro h; subst x; exact hvS hx      exact ⟨⟨x, by simp [A, hxne]⟩, by simp [S', hx]⟩    · intro x hx      have hxS : x.1 ∉ S := by simpa [S'] using hx      exact hdev.2.1 x.1 hxS    · rintro ⟨x, hxA⟩ hx      have hxS : x ∈ S := by simpa [S'] using hx      have hg := hdev.2.2 x hxS      have ha : (if G.Adj x v ∧ τ v ≠ τ x then 1 else 0 : ℕ) ≤          (if G.Adj x v ∧ σ v ≠ σ x then 1 else 0 : ℕ) := by        by_cases hadj : G.Adj x v        · have hp : σ v ≠ σ x := Ne.symm (hproper x (G.adj_symm hadj))          simp only [hadj, hp, true_and, if_true]          split <;> omega        · simp [hadj]      rw [hsplit σ x hxA, hsplit τ x hxA] at hg      omega  exact hsub S' (fun x => τ x.1) hdev'
See it in the graphDiscuss this resultChallenge it