AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_extend_low_degree_vertex

theoremverified

If a vertex has degree strictly smaller than the number k of available colors, a strong equilibrium of the induced graph obtained by deleting it extends to a strong equilibrium of the original finite graph.

Statement

theorem maxcut_strong_equilibrium_extend_low_degree_vertex
    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (v : V) (k : ℕ) (hd : G.degree v < k)
    (hsub : ∃ s : (↑(Finset.univ.erase v) : Set V) → Fin k,
      is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V)) s) :
    ∃ σ : V → Fin k, 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 2
Used by 1

The proof, explained

The proof extends a strong equilibrium s on G - v to the entire graph G by choosing an unused color for v. Since the degree of v is strictly less than the number k of available colors, its neighbors use strictly fewer than k distinct colors, leaving at least one color c unused. Assigning color c to v ensures that all incident edges to v are cut, so v achieves its maximum possible cut utility and can never participate in any improving coalition deviation; the theorem then follows from the key lemma maxcut_strong_equilibrium_of_saturated_vertex.

  1. Fix a strong equilibrium s on G - v, note k > 0, extend s to all vertices as s0, and collect the colors used by the neighbors of v.

    Using classical logic, let A = V \ {v} be the remaining vertices and unpack the assumed strong equilibrium s on the induced subgraph G[A]. Since the degree of v is strictly less than k and degrees are non-negative, linear arithmetic (via omega) yields 0 < k. We extend s to a total coloring s0 on V by assigning an arbitrary default color 0 to v, and define used as the image under s0 of the neighbor finset of v.

    lines 9–14

      classical
      let A : Finset V := Finset.univ.erase v
      obtain ⟨s, hs⟩ := hsub
      have hk : 0 < k := by omega
      let s0 : V → Fin k := fun w => if hw : w ∈ A then s ⟨w, hw⟩ else ⟨0, hk⟩
      let used := (G.neighborFinset v).image s0
  2. The number of distinct colors used by the neighbors of v is strictly less than k.

    The size of used cannot exceed the number of neighbors of v (by Finset.card_image_le). In turn, the number of neighbors equals the degree of v (by G.card_neighborFinset_eq_degree), which is strictly less than k = |Fin k| by the hypothesis hd.

    lines 15–19

    uses Finset.card_image_le, G.card_neighborFinset_eq_degree

      have hcard : used.card < Fintype.card (Fin k) := by
        calc
          used.card ≤ (G.neighborFinset v).card := Finset.card_image_le
          _ = G.degree v := G.card_neighborFinset_eq_degree v
          _ < Fintype.card (Fin k) := by simpa using hd
  3. There exists an available color c not used by any neighbor of v.

    By contradiction, suppose no such unused color exists. Then every color in Fin k is in used, making used equal to the universal set Finset.univ (by Finset.eq_univ_iff_forall.mpr). Its cardinality would then be k, contradicting |used| < k via Nat.lt_irrefl. Thus there is an unused color c.

    lines 20–26

    uses Finset.eq_univ_iff_forall.mpr, Nat.lt_irrefl

      have hc : ∃ c : Fin k, c ∉ used := by
        by_contra h
        push Not at h
        have heq : used = Finset.univ := Finset.eq_univ_iff_forall.mpr h
        rw [heq] at hcard
        exact (Nat.lt_irrefl _ hcard)
      obtain ⟨c, hc⟩ := hc
  4. Assigning color c to v and keeping the colors of all other vertices yields a coloring σ where every neighbor of v has a color different from v.

    Define σ by assigning c to v and s0(w) to every other vertex w. For any neighbor w of v, G.ne_of_adj ensures w ≠ v. Then s0(w) is in used (by Finset.mem_image.mpr and G.mem_neighborFinset), which means s0(w) ≠ c since c ∉ used. Therefore σ(w) ≠ σ(v), meaning all edges incident to v are cut.

    lines 27–37

    uses G.ne_of_adj, Finset.mem_image.mpr, G.mem_neighborFinset

      let σ : V → Fin k := fun w => if w = v then c else s0 w
      have hproper : ∀ w, G.Adj v w → σ w ≠ σ v := by
        intro w hw
        have hwne : w ≠ v := (G.ne_of_adj hw).symm
        have hwused : s0 w ∈ used := by
          exact Finset.mem_image.mpr ⟨w, (G.mem_neighborFinset v w).mpr hw, rfl⟩
        have hne : s0 w ≠ c := by
          intro heq
          apply hc
          simpa [heq] using hwused
        simpa [σ, hwne] using hne
  5. The restriction of σ to V \ {v} coincides with the original equilibrium s.

    For any element x in V \ {v}, x ≠ v by Finset.mem_erase.mp. Evaluating σ at x gives s0(x) = s(x), so the restriction is definitionally equal to s.

    lines 38–41

    uses Finset.mem_erase.mp

      have hs_eq : (fun x : (↑A : Set V) => σ x.1) = s := by
        funext x
        have hxne : x.1 ≠ v := (Finset.mem_erase.mp x.2).1
        simp [σ, s0, hxne, x.2]
  6. The extended coloring σ is a max-cut strong equilibrium of G.

    We provide σ as the existential witness using Exists.intro. Because σ cuts every edge incident to v, vertex v already attains its maximum possible utility (its degree), so it cannot strictly improve in any coalition deviation. By maxcut_strong_equilibrium_of_saturated_vertex, any such saturated extension of a strong equilibrium on G - v is a strong equilibrium of G.

    lines 42–44

    uses Exists.intro, maxcut_strong_equilibrium_of_saturated_vertex

      apply Exists.intro σ
      apply maxcut_strong_equilibrium_of_saturated_vertex G v σ hproper
      exact hs_eq ▸ hs
Finset.card_image_le
The size of the image of a finite set under a function is at most the size of the domain set.
G.card_neighborFinset_eq_degree
In a simple graph, the number of neighbors of a vertex equals its degree.
Finset.eq_univ_iff_forall.mpr
A finset in a finite type equals the universal finset if and only if it contains every element of the type.
Nat.lt_irrefl
Strict inequality on natural numbers is irreflexive: n < n is false for every n.
G.ne_of_adj
Adjacent vertices in a simple graph are distinct (no self-loops).
Finset.mem_image.mpr
An element b is in the image of s under f if there exists some a in s with f a = b.
G.mem_neighborFinset
A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Finset.mem_erase.mp
If an element belongs to s with v erased, it is distinct from v and belongs to s.
Exists.intro
Proves an existential proposition ∃ x, P x by providing an explicit witness w and a proof of P w.
maxcut_strong_equilibrium_of_saturated_vertex
If a coloring cuts every edge incident to a vertex v (so v achieves maximal cut utility) and restricts to a strong equilibrium on G - v, then it is a strong equilibrium of G.

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_extend_low_degree_vertex    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (v : V) (k : ℕ) (hd : G.degree v < k)    (hsub : ∃ s : (↑(Finset.univ.erase v) : Set V) → Fin k,      is_maxcut_strong_equilibrium (G.induce (↑(Finset.univ.erase v) : Set V)) s) :    ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by  classical  let A : Finset V := Finset.univ.erase v  obtain ⟨s, hs⟩ := hsub  have hk : 0 < k := by omega  let s0 : V → Fin k := fun w => if hw : w ∈ A then s ⟨w, hw⟩ else ⟨0, hk⟩  let used := (G.neighborFinset v).image s0  have hcard : used.card < Fintype.card (Fin k) := by    calc      used.card ≤ (G.neighborFinset v).card := Finset.card_image_le      _ = G.degree v := G.card_neighborFinset_eq_degree v      _ < Fintype.card (Fin k) := by simpa using hd  have hc : ∃ c : Fin k, c ∉ used := by    by_contra h    push Not at h    have heq : used = Finset.univ := Finset.eq_univ_iff_forall.mpr h    rw [heq] at hcard    exact (Nat.lt_irrefl _ hcard)  obtain ⟨c, hc⟩ := hc  let σ : V → Fin k := fun w => if w = v then c else s0 w  have hproper : ∀ w, G.Adj v w → σ w ≠ σ v := by    intro w hw    have hwne : w ≠ v := (G.ne_of_adj hw).symm    have hwused : s0 w ∈ used := by      exact Finset.mem_image.mpr ⟨w, (G.mem_neighborFinset v w).mpr hw, rfl⟩    have hne : s0 w ≠ c := by      intro heq      apply hc      simpa [heq] using hwused    simpa [σ, hwne] using hne  have hs_eq : (fun x : (↑A : Set V) => σ x.1) = s := by    funext x    have hxne : x.1 ≠ v := (Finset.mem_erase.mp x.2).1    simp [σ, s0, hxne, x.2]  apply Exists.intro σ  apply maxcut_strong_equilibrium_of_saturated_vertex G v σ hproper  exact hs_eq ▸ hs
See it in the graphDiscuss this resultChallenge it