AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_reduce_vertex_deletions

theoremverified

Fix k. If every finite graph 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_vertex_deletions (k : ℕ)
    (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],
      (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) →
      ∃ σ : 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 3

The proof, explained

The proof reduces the existence of strong k-color equilibria for general finite graphs to graphs whose single-vertex deletions are preconnected. First, `maxcut_strong_equilibrium_reduce_single_vertex_sums` reduces the problem to graphs that are indecomposable under 1-sums (clique-sums over a single vertex). Second, `maxcut_one_sum_indecomposable_delete_preconnected` shows that deleting any vertex from such a 1-sum indecomposable graph leaves a preconnected subgraph. Finally, the assumption `hbase` directly supplies the required strong equilibrium.

  1. It suffices to prove the existence of a strong k-color equilibrium for graphs that are indecomposable under 1-sums.

    By `maxcut_strong_equilibrium_reduce_single_vertex_sums`, the theorem reduces to showing that an equilibrium exists for every graph G that cannot be non-trivially split into two subgraphs A and B meeting at a single vertex o with no edges connecting A \ {o} and B \ {o}.

    line 9

    uses maxcut_strong_equilibrium_reduce_single_vertex_sums

      apply maxcut_strong_equilibrium_reduce_single_vertex_sums k
  2. Every finite 1-sum indecomposable graph has a strong k-color equilibrium.

    Let G be a finite graph satisfying the 1-sum indecomposability condition (hind). By `maxcut_one_sum_indecomposable_delete_preconnected`, deleting any vertex o from G leaves a preconnected induced subgraph. This satisfies the precondition of the hypothesis hbase, which then directly provides a strong k-color equilibrium for G.

    lines 10–11

    uses maxcut_one_sum_indecomposable_delete_preconnected

      intro V _ _ G _ hind
      exact hbase V G (maxcut_one_sum_indecomposable_delete_preconnected G hind)
maxcut_strong_equilibrium_reduce_single_vertex_sums
If every finite graph that cannot be decomposed into two subgraphs meeting at a single vertex with no edges between them admits a strong k-color equilibrium, then every finite graph admits a strong k-color equilibrium.
maxcut_one_sum_indecomposable_delete_preconnected
In a finite graph that cannot be non-trivially decomposed into two subgraphs intersecting at a single vertex with no edges between them, deleting any single vertex leaves a preconnected induced 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_vertex_deletions (k : ℕ)    (hbase : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],      (∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected) →      ∃ σ : 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_single_vertex_sums k  intro V _ _ G _ hind  exact hbase V G (maxcut_one_sum_indecomposable_delete_preconnected G hind)
See it in the graphDiscuss this resultChallenge it