AFTD Auto-Formalizing Theoretical Domains

maxcut_defect_one_dense_core_witness

theoremverified

A 12-vertex graph of minimum degree nine has a six-clique, a 1-defective 3-coloring, and a strong 3-color equilibrium.

Statement

theorem maxcut_defect_one_dense_core_witness :
    (∀ v : Fin 12, (Finset.univ.filter fun w => maxcut_defect_one_dense_core_graph.Adj v w ∧
      maxcut_defect_one_dense_core_coloring w = maxcut_defect_one_dense_core_coloring v).card ≤ 1) ∧
    (∀ v : Fin 12, 9 ≤ maxcut_defect_one_dense_core_graph.degree v) ∧
    (∀ u ∈ ({0, 1, 4, 5, 8, 9} : Finset (Fin 12)),
      ∀ v ∈ ({0, 1, 4, 5, 8, 9} : Finset (Fin 12)),
      u ≠ v → maxcut_defect_one_dense_core_graph.Adj u v) ∧
    ∃ σ : Fin 12 → Fin 3, is_maxcut_strong_equilibrium maxcut_defect_one_dense_core_graph σ
Source
Explicit dense-core example investigated in experiment 16301.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

Lean source view module on GitHub

set_option maxRecDepth 8192
set_option maxHeartbeats 12000000
instance : DecidableRel maxcut_defect_one_dense_core_graph.Adj := by
  unfold maxcut_defect_one_dense_core_graph
  infer_instance

theorem maxcut_defect_one_dense_core_witness :
    (∀ v : Fin 12, (Finset.univ.filter fun w => maxcut_defect_one_dense_core_graph.Adj v w ∧
      maxcut_defect_one_dense_core_coloring w = maxcut_defect_one_dense_core_coloring v).card ≤ 1) ∧
    (∀ v : Fin 12, 9 ≤ maxcut_defect_one_dense_core_graph.degree v) ∧
    (∀ u ∈ ({0, 1, 4, 5, 8, 9} : Finset (Fin 12)),
      ∀ v ∈ ({0, 1, 4, 5, 8, 9} : Finset (Fin 12)),
      u ≠ v → maxcut_defect_one_dense_core_graph.Adj u v) ∧
    ∃ σ : Fin 12 → Fin 3, is_maxcut_strong_equilibrium maxcut_defect_one_dense_core_graph σ := by
  have h :
      (∀ v : Fin 12, (Finset.univ.filter fun w => maxcut_defect_one_dense_core_graph.Adj v w ∧
        maxcut_defect_one_dense_core_coloring w = maxcut_defect_one_dense_core_coloring v).card ≤ 1) ∧
      (∀ v : Fin 12, 9 ≤ maxcut_defect_one_dense_core_graph.degree v) ∧
      (∀ u ∈ ({0, 1, 4, 5, 8, 9} : Finset (Fin 12)),
        ∀ v ∈ ({0, 1, 4, 5, 8, 9} : Finset (Fin 12)),
        u ≠ v → maxcut_defect_one_dense_core_graph.Adj u v) := by decide
  refine ⟨h.1, h.2.1, h.2.2, ?_⟩
  exact (maxcut_strong_equilibrium_of_defect_one maxcut_defect_one_dense_core_graph
    ⟨maxcut_defect_one_dense_core_coloring, h.1⟩).imp (fun _ h => h.1)
See it in the graphDiscuss this resultChallenge it