AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_reduce_dense_core

theoremverified

Fix k at least three. If every finite graph of minimum degree at least k, with preconnected vertex deletions and with some vertex of degree at least 2k, has a strong k-color equilibrium, then every finite graph has a strong k-color equilibrium.

Statement

theorem maxcut_strong_equilibrium_reduce_dense_core (k : ℕ) (hk : 3 ≤ 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 : V, 2 * 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 question in arXiv:2610.04948, Section 4.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

The proof reduces the existence of strong k-color equilibria on arbitrary finite graphs to graphs with minimum degree at least k and preconnected vertex deletions, using maxcut_strong_equilibrium_reduce_connected_core. It then splits into two cases based on whether G has a vertex of degree at least 2k. If such a vertex exists, the assumed hypothesis hbase directly supplies a strong equilibrium; otherwise, every vertex has degree at most 2k - 1, and the bounded-degree result maxcut_op89_exists_of_max_degree_le provides an optimal strong equilibrium.

  1. It suffices to show the existence of a strong k-color equilibrium for finite graphs with preconnected vertex deletions and minimum degree at least k.

    Applying the reduction theorem maxcut_strong_equilibrium_reduce_connected_core reduces the claim for all finite graphs to those whose single-vertex deletions are preconnected and where every vertex has degree at least k. We then fix an arbitrary finite graph G on vertex type V with these properties (named hpre and hmin).

    lines 8–9

    uses maxcut_strong_equilibrium_reduce_connected_core

      apply maxcut_strong_equilibrium_reduce_connected_core
      intro V _ _ G _ hpre hmin
  2. If G has a vertex of degree at least 2k, G has a strong k-color equilibrium.

    We perform a case split on whether there exists a vertex v with degree at least 2k. In the positive branch, all preconditions of the hypothesis hbase (preconnected vertex deletions, minimum degree at least k, and maximum degree at least 2k) are satisfied, so hbase immediately yields the desired equilibrium.

    lines 10–11

      by_cases hmax : ∃ v : V, 2 * k ≤ G.degree v
      · exact hbase V G hpre hmin hmax
  3. In the negative branch, every vertex of G has degree at most 2k - 1.

    Assuming no vertex has degree at least 2k, it follows that ¬(2k ≤ degree(v)) for each v. Linear arithmetic over ℕ (closed by omega) turns this into degree(v) ≤ 2k - 1.

    lines 12–15

      · have hdeg : ∀ v : V, G.degree v ≤ 2 * k - 1 := by
          intro v
          have : ¬ (2 * k ≤ G.degree v) := fun h => hmax ⟨v, h⟩
          omega
  4. A strong k-color equilibrium exists for G when the maximum degree is at most 2k - 1.

    Because k ≥ 3 and every vertex has degree at most 2k - 1, the lemma maxcut_op89_exists_of_max_degree_le guarantees the existence of a coloring σ that is an optimal strong equilibrium. Extracting σ and its strong equilibrium property completes the proof.

    lines 16–18

    uses maxcut_op89_exists_of_max_degree_le

        have hopt := maxcut_op89_exists_of_max_degree_le G k hk hdeg
        rcases hopt with ⟨σ, _, hse⟩
        exact ⟨σ, hse⟩
maxcut_strong_equilibrium_reduce_connected_core
For any natural number k, if every finite graph with preconnected single-vertex deletions and minimum degree at least k has a strong k-color equilibrium, then all finite graphs have a strong k-color equilibrium.
maxcut_op89_exists_of_max_degree_le
For k ≥ 3, any finite graph with maximum degree at most 2k - 1 has an optimal strong k-color 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

theorem maxcut_strong_equilibrium_reduce_dense_core (k : ℕ) (hk : 3 ≤ 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 : V, 2 * 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  apply maxcut_strong_equilibrium_reduce_connected_core  intro V _ _ G _ hpre hmin  by_cases hmax : ∃ v : V, 2 * k ≤ G.degree v  · exact hbase V G hpre hmin hmax  · have hdeg : ∀ v : V, G.degree v ≤ 2 * k - 1 := by      intro v      have : ¬ (2 * k ≤ G.degree v) := fun h => hmax ⟨v, h⟩      omega    have hopt := maxcut_op89_exists_of_max_degree_le G k hk hdeg    rcases hopt with ⟨σ, _, hse⟩    exact ⟨σ, hse⟩
See it in the graphDiscuss this resultChallenge it