AFTD Auto-Formalizing Theoretical Domains

maxcut_pinned_twins_not_colorable_three

theoremverified

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

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.

  1. 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.

    lines 1–4

    private instance maxcut_pinned_twins_not_colorable_three_dec :
        DecidableRel maxcut_pinned_twins_graph.Adj := by
      unfold maxcut_pinned_twins_graph
      infer_instance
  2. 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.

    lines 6–7

    theorem maxcut_pinned_twins_not_colorable_three : ¬ maxcut_pinned_twins_graph.Colorable 3 := by
      rintro ⟨C⟩
  3. 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`).

    line 8

      have hfin : ∀ a b y z : Fin 3, y ≠ z → a ≠ y → a ≠ z → b ≠ y → b ≠ z → a = b := by decide
  4. 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`).

    lines 9–14

      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
  5. 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.

    line 15

      exact C.valid h6 (hfin _ _ _ _ (C.valid h1) (C.valid h2) (C.valid h3) (C.valid h4) (C.valid h5))

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 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))
See it in the graphDiscuss this resultChallenge it