maxcut_pinned_twins_not_colorable_three
The 182-vertex pinned twins graph maxcut_pinned_twins_graph is not 3-colorable.
Statement
theorem maxcut_pinned_twins_not_colorable_three : ¬ maxcut_pinned_twins_graph.Colorable 3- Source
- Hypothesis check for the refutation of maxcut_op89_residual_exists (OP-89, arXiv:2610.04948).
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- maxcut_pinned_twins_graphA candidate counterexample graph on 182 vertices. Replace each vertex of the paper graph G_3 by two independent twins, replace each old…
- Used by 1
- maxcut_op89_residual_exists_negationThe residual case maxcut_op89_residual_exists of OP-89 is false: it is not true that every finite simple graph G with k ≥ 3, at least 2k+2…
The proof, explained
The theorem is proved by contradiction: suppose the pinned twins graph admits a proper 3-coloring. By finite computation (`decide`), the graph contains a complete 4-vertex subgraph ($K_4$) spanned by vertices $(\text{inl } 0, 0)$, $(\text{inl } 5, 0)$, $(\text{inr } (1, 0), 0)$, and $(\text{inr } (2, 0), 0)$. In any proper coloring with 3 colors, two adjacent vertices of this clique must receive two distinct colors, which forces the remaining two mutually adjacent vertices to share the single remaining color, contradicting properness of the coloring.
The adjacency relation of `maxcut_pinned_twins_graph` is decidable.
We establish a `DecidableRel` instance for edge adjacency in the graph by unfolding the graph definition to its underlying relation on finite types and invoking typeclass resolution.
private instance maxcut_pinned_twins_not_colorable_three_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instance
Assume for contradiction that the graph admits a proper 3-coloring.
We set up a proof by contradiction: suppose there exists a valid 3-coloring $C$, assigning each vertex a color in $\mathrm{Fin}\; 3$ such that adjacent vertices always receive different colors.
theorem maxcut_pinned_twins_not_colorable_three : ¬ maxcut_pinned_twins_graph.Colorable 3 := by rintro ⟨C⟩
In any 3-element set of colors, elements avoiding two distinct colors are uniquely determined.
We prove the combinatorial lemma `hfin`: for any $a, b, y, z \in \mathrm{Fin}\; 3$, if $y \neq z$ and both $a$ and $b$ are distinct from both $y$ and $z$, then $a = b$. Since $\mathrm{Fin}\; 3$ has only three elements, excluding two distinct values leaves exactly one possibility. This finite truth is discharged by computation (`decide`).
have hfin : ∀ a b y z : Fin 3, y ≠ z → a ≠ y → a ≠ z → b ≠ y → b ≠ z → a = b := by decide
The four vertices $u = (\text{inl } 0, 0)$, $v = (\text{inl } 5, 0)$, $w_1 = (\text{inr } (1, 0), 0)$, and $w_2 = (\text{inr } (2, 0), 0)$ form a 4-clique ($K_4$).
We verify that all $\binom{4}{2} = 6$ edges among these four vertices are present in the graph: $w_1 \sim w_2$ (`h1`), $u \sim w_1$ (`h2`), $u \sim w_2$ (`h3`), $v \sim w_1$ (`h4`), $v \sim w_2$ (`h5`), and $u \sim v$ (`h6`). Each edge assertion is proven by direct computation (`decide`).
have h1 : maxcut_pinned_twins_graph.Adj (.inr (1, 0), 0) (.inr (2, 0), 0) := by decide have h2 : maxcut_pinned_twins_graph.Adj (.inl 0, 0) (.inr (1, 0), 0) := by decide have h3 : maxcut_pinned_twins_graph.Adj (.inl 0, 0) (.inr (2, 0), 0) := by decide have h4 : maxcut_pinned_twins_graph.Adj (.inl 5, 0) (.inr (1, 0), 0) := by decide have h5 : maxcut_pinned_twins_graph.Adj (.inl 5, 0) (.inr (2, 0), 0) := by decide have h6 : maxcut_pinned_twins_graph.Adj (.inl 0, 0) (.inl 5, 0) := by decide
Contradiction.
Because $w_1$ and $w_2$ are adjacent (`h1`), their colors $C(w_1)$ and $C(w_2)$ are distinct. Since $u$ is adjacent to both $w_1$ and $w_2$ (`h2`, `h3`), $C(u)$ must differ from both $C(w_1)$ and $C(w_2)$. Similarly, since $v$ is adjacent to both (`h4`, `h5`), $C(v)$ must also differ from both. By `hfin`, this forces $C(u) = C(v)$. But $u$ and $v$ are adjacent (`h6`), so $C(u) \neq C(v)$ by properness of the coloring, yielding False.
exact C.valid h6 (hfin _ _ _ _ (C.valid h1) (C.valid h2) (C.valid h3) (C.valid h4) (C.valid h5))
- The proof does not need to analyze the full 182-vertex graph; it simply exhibits an explicit 4-vertex complete subgraph (a $K_4$) verified by computation, which immediately prevents 3-colorability.
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 maxcut_pinned_twins_not_colorable_three_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instancetheorem maxcut_pinned_twins_not_colorable_three : ¬ maxcut_pinned_twins_graph.Colorable 3 := by rintro ⟨C⟩ have hfin : ∀ a b y z : Fin 3, y ≠ z → a ≠ y → a ≠ z → b ≠ y → b ≠ z → a = b := by decide have h1 : maxcut_pinned_twins_graph.Adj (.inr (1, 0), 0) (.inr (2, 0), 0) := by decide have h2 : maxcut_pinned_twins_graph.Adj (.inl 0, 0) (.inr (1, 0), 0) := by decide have h3 : maxcut_pinned_twins_graph.Adj (.inl 0, 0) (.inr (2, 0), 0) := by decide have h4 : maxcut_pinned_twins_graph.Adj (.inl 5, 0) (.inr (1, 0), 0) := by decide have h5 : maxcut_pinned_twins_graph.Adj (.inl 5, 0) (.inr (2, 0), 0) := by decide have h6 : maxcut_pinned_twins_graph.Adj (.inl 0, 0) (.inl 5, 0) := by decide exact C.valid h6 (hfin _ _ _ _ (C.valid h1) (C.valid h2) (C.valid h3) (C.valid h4) (C.valid h5))