maxcut_fair9_not_three_colorable
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.
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.
private instance : DecidableRel maxcut_fair9_graph.Adj := by unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instance
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.
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
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.
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σ⟩
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.
uses
maxcut_fair9_not_three_colorable_clique_4exact 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.
- The decidability of graph adjacency is registered as a typeclass instance using `infer_instance` after unfolding the graph definition, allowing the subsequent six edge membership checks to be discharged automatically by `decide`.
- The helper lemma `maxcut_fair9_not_three_colorable_clique_4` proves that a 4-clique cannot be 3-colored via exhaustive case analysis (`fin_cases`) over all 81 possible color assignments, rather than by invoking a general pigeonhole principle lemma.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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))