AFTD Auto-Formalizing Theoretical Domains

maxcut_fair9_not_three_colorable

theoremverified

The specified nine-vertex fairness-obstruction graph does not admit a proper coloring with three colors.

Statement

theorem maxcut_fair9_not_three_colorable :
    ¬ ∃ σ : Fin 9 → Fin 3, ∀ v w : Fin 9, maxcut_fair9_graph.Adj v w → σ v ≠ σ w
Source
Experiment 12998 identifies a four-vertex clique in the finite fairness obstruction related to OP-85.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • maxcut_fair9_graphThe explicit nine-vertex simple graph used to obstruct fair Nash selection.

The proof, explained

The theorem is proved by contradiction by identifying an obstruction: the nine-vertex graph contains a 4-clique (a complete subgraph K₄) on vertices 3, 4, 5, and 8. A helper lemma establishes the pigeonhole principle for four elements in a three-element set, showing that no four elements of Fin 3 can be pairwise distinct. Assuming a proper 3-coloring exists, every pair among these four vertices is adjacent and must therefore receive different colors. Evaluating the six adjacency conditions by computation and applying the helper lemma to the four resulting distinct colors produces a contradiction.

  1. Adjacency in maxcut_fair9_graph is computationally decidable.

    Unfolding the definitions of maxcut_fair9_graph and SimpleGraph.fromRel reveals that adjacency reduces to checking membership in a explicit finite list of pairs. Typeclass inference (`infer_instance`) automatically synthesizes the DecidableRel instance.

    lines 1–3

    private instance : DecidableRel maxcut_fair9_graph.Adj := by
      unfold maxcut_fair9_graph SimpleGraph.fromRel
      infer_instance
  2. No four elements of a 3-element set can be pairwise distinct.

    We perform exhaustive case analysis over all 3⁴ = 81 possible assignments of values in Fin 3 to the four variables a, b, c, d using `fin_cases`. In every case, at least two variables receive the same value, directly contradicting one of the six pairwise distinctness hypotheses hab, hac, had, hbc, hbd, hcd, which `contradiction` detects.

    lines 5–8

    lemma maxcut_fair9_not_three_colorable_clique_4 (a b c d : Fin 3)
        (hab : a ≠ b) (hac : a ≠ c) (had : a ≠ d)
        (hbc : b ≠ c) (hbd : b ≠ d) (hcd : c ≠ d) : False := by
      fin_cases a <;> fin_cases b <;> fin_cases c <;> fin_cases d <;> contradiction
  3. Assume for contradiction that maxcut_fair9_graph has a proper 3-coloring.

    We introduce the assumption that there exists a coloring σ : Fin 9 → Fin 3 such that any two adjacent vertices receive different colors.

    lines 10–12

    theorem maxcut_fair9_not_three_colorable :
        ¬ ∃ σ : Fin 9 → Fin 3, ∀ v w : Fin 9, maxcut_fair9_graph.Adj v w → σ v ≠ σ w := by
      intro ⟨σ, hσ⟩
  4. Vertices 3, 4, 5, and 8 form a 4-clique, contradicting the 3-colorability assumption.

    The six pairs between vertices 3, 4, 5, and 8 are all edges of the graph, each verified by computational reflection (`by decide`). Since σ is assumed to be a proper coloring, the colors σ(3), σ(4), σ(5), and σ(8) must be pairwise distinct. Applying lemma maxcut_fair9_not_three_colorable_clique_4 to these four colors produces a contradiction.

    lines 13–15

    uses maxcut_fair9_not_three_colorable_clique_4

      exact maxcut_fair9_not_three_colorable_clique_4 (σ 3) (σ 4) (σ 5) (σ 8)
        (hσ 3 4 (by decide)) (hσ 3 5 (by decide)) (hσ 3 8 (by decide))
        (hσ 4 5 (by decide)) (hσ 4 8 (by decide)) (hσ 5 8 (by decide))
maxcut_fair9_not_three_colorable_clique_4
Four elements of a three-element set cannot be pairwise distinct: given four elements of Fin 3 and proofs that all six pairs are distinct, a contradiction (False) is derived.

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

private instance : DecidableRel maxcut_fair9_graph.Adj := by  unfold maxcut_fair9_graph SimpleGraph.fromRel  infer_instancelemma maxcut_fair9_not_three_colorable_clique_4 (a b c d : Fin 3)    (hab : a ≠ b) (hac : a ≠ c) (had : a ≠ d)    (hbc : b ≠ c) (hbd : b ≠ d) (hcd : c ≠ d) : False := by  fin_cases a <;> fin_cases b <;> fin_cases c <;> fin_cases d <;> contradictiontheorem maxcut_fair9_not_three_colorable :    ¬ ∃ σ : Fin 9 → Fin 3, ∀ v w : Fin 9, maxcut_fair9_graph.Adj v w → σ v ≠ σ w := by  intro ⟨σ, hσ⟩  exact maxcut_fair9_not_three_colorable_clique_4 (σ 3) (σ 4) (σ 5) (σ 8)    (hσ 3 4 (by decide)) (hσ 3 5 (by decide)) (hσ 3 8 (by decide))    (hσ 4 5 (by decide)) (hσ 4 8 (by decide)) (hσ 5 8 (by decide))
See it in the graphDiscuss this resultChallenge it