AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_reduce_single_vertex_sums

theoremverified

For any fixed number of colors, if every finite graph with decidable equality and adjacency that has no nontrivial separation into two induced pieces meeting at one vertex has a strong equilibrium, then every finite graph with decidable equality and adjacency has a strong equilibrium. A separation is nontrivial when neither piece contains all vertices and there are no edges between the exclusive parts.

Statement

theorem maxcut_strong_equilibrium_reduce_single_vertex_sums (k : ℕ)
    (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],
      (∀ (A B : Finset V) (o : V), A ∪ B = Finset.univ → A ∩ B = {o} →
        (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) →
        A = Finset.univ ∨ B = Finset.univ) →
      ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ) :
    ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],
      ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ
Source
Structural reduction for OP-85, the strong-equilibrium existence problem; the two-piece gluing step is maxcut_single_vertex_sum_strong_equilibrium.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The proof proceeds by strong induction on the number of vertices n of the graph. If the graph admits a nontrivial single-vertex separation into two proper pieces with no edges between their disjoint parts, both pieces have strictly fewer vertices, so by the induction hypothesis each admits a strong equilibrium; these are then glued together into a strong equilibrium for the whole graph. Otherwise, the graph has no nontrivial single-vertex separation, so the base hypothesis immediately yields a strong equilibrium.

  1. To prove the theorem, it suffices to prove by strong induction on n that every graph on at most n vertices has a strong equilibrium.

    We introduce an auxiliary property h stating that every finite graph G with |V| ≤ n has a strong k-color max-cut equilibrium. We proceed by strong induction on n using Nat.strong_induction_on, which provides the induction hypothesis ih that the property holds for all m < n. We then consider a graph G on a vertex type V satisfying |V| ≤ n.

    lines 11–17

    uses Nat.strong_induction_on

      classical
      have h : ∀ n : ℕ, ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],
          Fintype.card V ≤ n → ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by
        intro n
        induction n using Nat.strong_induction_on with
        | h n ih =>
          intro V _ _ G _ hn
  2. The inductive step reduces to two cases: either G admits a nontrivial single-vertex separation, or it does not.

    We split into cases (using by_cases) on the existence of subsets A, B ⊆ V and a vertex o ∈ V covering V and intersecting only at o, with no edges between A \\ B and B \\ A, such that neither A nor B is all of V.

    lines 18–20

          by_cases hs : ∃ (A B : Finset V) (o : V), A ∪ B = Finset.univ ∧ A ∩ B = {o} ∧
              (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) ∧
              A ≠ Finset.univ ∧ B ≠ Finset.univ
  3. If G admits a nontrivial single-vertex separation, then G has a strong equilibrium.

    Given the separation into A and B meeting at o, since A ≠ V and B ≠ V, both A and B are strict subsets of V and therefore have strictly fewer than |V| ≤ n vertices by Finset.card_lt_card, Finset.ssubset_iff_subset_ne.mpr, Finset.subset_univ, and lt_of_lt_of_le. Applying the induction hypothesis ih to the induced subgraphs on A and B yields strong equilibria ea and eb on each piece. Finally, maxcut_single_vertex_sum_strong_equilibrium_exists combines these two equilibria into a strong equilibrium on G.

    lines 21–30

    uses lt_of_lt_of_le, Finset.card_lt_card, Finset.ssubset_iff_subset_ne.mpr, Finset.subset_univ, le_refl, maxcut_single_vertex_sum_strong_equilibrium_exists

          · obtain ⟨A, B, o, hcover, hinter, hsep, hA, hB⟩ := hs
            have hcardA : Fintype.card (↑A : Set V) < n := by
              apply lt_of_lt_of_le _ hn
              simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ A, hA⟩)
            have hcardB : Fintype.card (↑B : Set V) < n := by
              apply lt_of_lt_of_le _ hn
              simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ B, hB⟩)
            have ea := ih _ hcardA (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _)
            have eb := ih _ hcardB (↑B : Set V) (G.induce (↑B : Set V)) (le_refl _)
            exact maxcut_single_vertex_sum_strong_equilibrium_exists G A B o k hcover hinter hsep ea eb
  4. If G admits no nontrivial single-vertex separation, then G has a strong equilibrium.

    When G has no nontrivial single-vertex separation, it satisfies the premise of the base hypothesis hbase. Indeed, if there were any single-vertex separation with A ≠ V and B ≠ V, this would contradict the negation of hs. Thus hbase directly supplies a strong equilibrium for G.

    lines 31–35

          · apply hbase V G
            intro A B o hc hi hn
            by_contra hbad
            push Not at hbad
            exact hs ⟨A, B, o, hc, hi, hn, hbad.1, hbad.2⟩
  5. Every finite graph has a strong equilibrium.

    Given an arbitrary finite graph G on vertex set V, we apply the auxiliary inductive result h with n = |V| and the trivial bound |V| ≤ |V| provided by le_refl.

    lines 36–37

    uses le_refl

      intro V _ _ G _
      exact h (Fintype.card V) V G (le_refl _)
Nat.strong_induction_on
The principle of strong induction on ℕ: to prove P(n) for all n, it suffices to prove P(n) under the assumption that P(m) holds for all m < n.
lt_of_lt_of_le
Transitivity of strict and non-strict inequality: if a < b and b ≤ c, then a < c.
Finset.card_lt_card
A strictly smaller finite set has strictly smaller cardinality: if s ⊂ t, then |s| < |t|.
Finset.ssubset_iff_subset_ne.mpr
If s ⊆ t and s ≠ t, then s is a strict subset of t (s ⊂ t).
Finset.subset_univ
Every finset of elements from a finite type is a subset of the universal finset.
le_refl
Reflexivity of the partial order ≤: for any a, a ≤ a.
maxcut_single_vertex_sum_strong_equilibrium_exists
If a graph is decomposed into two induced subgraphs on vertex subsets A and B that cover all vertices, intersect at a single vertex, and have no edges between A \\ B and B \\ A, and if both induced subgraphs admit a strong max-cut equilibrium, then the whole graph admits a strong max-cut equilibrium.

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_reduce_single_vertex_sums (k : ℕ)    (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],      (∀ (A B : Finset V) (o : V), A ∪ B = Finset.univ → A ∩ B = {o} →        (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) →        A = Finset.univ ∨ B = Finset.univ) →      ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ) :    ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],      ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by  classical  have h : ∀ n : ℕ, ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],      Fintype.card V ≤ n → ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ := by    intro n    induction n using Nat.strong_induction_on with    | h n ih =>      intro V _ _ G _ hn      by_cases hs : ∃ (A B : Finset V) (o : V), A ∪ B = Finset.univ ∧ A ∩ B = {o} ∧          (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) ∧          A ≠ Finset.univ ∧ B ≠ Finset.univ      · obtain ⟨A, B, o, hcover, hinter, hsep, hA, hB⟩ := hs        have hcardA : Fintype.card (↑A : Set V) < n := by          apply lt_of_lt_of_le _ hn          simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ A, hA⟩)        have hcardB : Fintype.card (↑B : Set V) < n := by          apply lt_of_lt_of_le _ hn          simpa using Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ B, hB⟩)        have ea := ih _ hcardA (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _)        have eb := ih _ hcardB (↑B : Set V) (G.induce (↑B : Set V)) (le_refl _)        exact maxcut_single_vertex_sum_strong_equilibrium_exists G A B o k hcover hinter hsep ea eb      · apply hbase V G        intro A B o hc hi hn        by_contra hbad        push Not at hbad        exact hs ⟨A, B, o, hc, hi, hn, hbad.1, hbad.2⟩  intro V _ _ G _  exact h (Fintype.card V) V G (le_refl _)
See it in the graphDiscuss this resultChallenge it