AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_reduce_connected_core

theoremverified

Fix k. If every finite graph of minimum degree at least k whose every vertex deletion is preconnected has a strong k-color equilibrium, then every finite graph has a strong k-color equilibrium.

Statement

theorem maxcut_strong_equilibrium_reduce_connected_core (k : ℕ)
    (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],
      (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) →
      (∀ v : V, k ≤ G.degree v) →
      ∃ σ : 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 unweighted Max-k-Cut strong-equilibrium existence problem in arXiv:2610.04948, Section 4.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

The theorem is proved by strong induction on the number of vertices |V| of a finite graph G. If G has a vertex v with degree less than k, removing v yields a strictly smaller graph that has an equilibrium by induction, which extends to v. If G decomposes into a non-trivial 1-sum of two subgraphs sharing a single vertex, the induction hypothesis provides equilibria on both pieces that can be glued together. Otherwise, G has minimum degree at least k and is 1-sum indecomposable (meaning every single-vertex deletion is preconnected), so the result follows directly from the assumed base hypothesis.

  1. It suffices to prove by strong induction on n that every finite graph G with |V| ≤ n has a strong k-color equilibrium.

    We activate classical logic and state the inductive assertion h for graphs of size bounded by n. Using strong induction on n (via Nat.strong_induction_on), we assume as induction hypothesis (ih) that every graph with strictly fewer than n vertices has a strong k-color equilibrium, and then introduce an arbitrary graph G with |V| ≤ n.

    lines 10–16

    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. If G has a vertex of degree strictly less than k, then G has a strong k-color equilibrium.

    Suppose there is a vertex v with deg(v) < k. We remove v to form the induced subgraph on A = V \ {v}. Since v ∉ A, A is a proper subset of V, so |A| < |V| ≤ n. By the induction hypothesis, G[A] admits a strong k-color equilibrium. Because deg(v) < k, maxcut_strong_equilibrium_extend_low_degree_vertex extends this coloring to v, yielding a strong k-color equilibrium on G.

    lines 17–28

    uses mem_univ, lt_of_lt_of_le, Finset.card_lt_card, Finset.ssubset_iff_subset_ne.mpr, Finset.subset_univ, le_refl, maxcut_strong_equilibrium_extend_low_degree_vertex

          by_cases hlow : ∃ v : V, G.degree v < k
          · obtain ⟨v, hv⟩ := hlow
            let A : Finset V := Finset.univ.erase v
            have hne : A ≠ Finset.univ := by
              intro he
              have hvA : v ∈ A := by rw [he]; exact mem_univ v
              simpa [A] using hvA
            have hcard : 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, hne⟩)
            have hex := ih _ hcard (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _)
            exact maxcut_strong_equilibrium_extend_low_degree_vertex G v k hv hex
  3. If G decomposes as a non-trivial 1-sum over a cut vertex, then G has a strong k-color equilibrium.

    Suppose V splits into two proper subgraphs A, B ⊊ V that overlap only at a single vertex o (A ∩ B = {o}) with no edges between A \ {o} and B \ {o}. Because A and B are proper subsets of V, their sizes are strictly less than n. The induction hypothesis provides strong k-color equilibria on both G[A] and G[B]. By maxcut_single_vertex_sum_strong_equilibrium_exists, these two equilibria can be glued at o to form a strong k-color equilibrium on G.

    lines 29–41

    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

          · 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
  4. If neither reduction applies, G satisfies the base hypothesis and therefore has a strong k-color equilibrium.

    When there are no vertices of degree less than k and no 1-sum decompositions, the minimum degree of G is at least k. Furthermore, by maxcut_one_sum_indecomposable_delete_preconnected, 1-sum indecomposability implies that deleting any vertex o leaves a preconnected induced subgraph. Hence G meets all premises of the base assumption hbase, which supplies the strong k-color equilibrium.

    lines 42–50

    uses maxcut_one_sum_indecomposable_delete_preconnected

            · apply hbase V G
              · apply maxcut_one_sum_indecomposable_delete_preconnected G
                intro A B o hc hi hsep
                by_contra hbad
                push Not at hbad
                exact hs ⟨A, B, o, hc, hi, hsep, hbad.1, hbad.2⟩
              · intro v
                by_contra hn
                exact hlow ⟨v, by omega⟩
  5. Every finite graph has a strong k-color equilibrium.

    Given any finite graph G on vertex set V, we apply the general result h with n = |V| and the trivial inequality |V| ≤ |V|, concluding the theorem.

    lines 51–52

    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 natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
mem_univ
Every element of a finite type belongs to its universal finset.
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 proper subset of a finite set has strictly smaller cardinality.
Finset.ssubset_iff_subset_ne.mpr
If a subset is not equal to the whole set, it is a proper (strict) subset.
Finset.subset_univ
Every finset in a finite type is a subset of the universal finset.
le_refl
Reflexivity of inequality: a ≤ a for all a.
maxcut_strong_equilibrium_extend_low_degree_vertex
If a vertex v has degree strictly less than k, any strong k-color equilibrium on G \ {v} extends to a strong k-color equilibrium on G.
maxcut_single_vertex_sum_strong_equilibrium_exists
If a graph is a 1-sum of two induced subgraphs A and B meeting at a single vertex o, strong k-color equilibria on G[A] and G[B] combine into a strong k-color equilibrium on G.
maxcut_one_sum_indecomposable_delete_preconnected
If a graph cannot be non-trivially decomposed as a 1-sum at any vertex, then deleting any single vertex yields a preconnected subgraph.

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_connected_core (k : ℕ)    (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],      (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) →      (∀ v : V, k ≤ G.degree v) →      ∃ σ : 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 hlow : ∃ v : V, G.degree v < k      · obtain ⟨v, hv⟩ := hlow        let A : Finset V := Finset.univ.erase v        have hne : A ≠ Finset.univ := by          intro he          have hvA : v ∈ A := by rw [he]; exact mem_univ v          simpa [A] using hvA        have hcard : 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, hne⟩)        have hex := ih _ hcard (↑A : Set V) (G.induce (↑A : Set V)) (le_refl _)        exact maxcut_strong_equilibrium_extend_low_degree_vertex G v k hv hex      · 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          · apply maxcut_one_sum_indecomposable_delete_preconnected G            intro A B o hc hi hsep            by_contra hbad            push Not at hbad            exact hs ⟨A, B, o, hc, hi, hsep, hbad.1, hbad.2⟩          · intro v            by_contra hn            exact hlow ⟨v, by omega⟩  intro V _ _ G _  exact h (Fintype.card V) V G (le_refl _)
See it in the graphDiscuss this resultChallenge it