AFTD Auto-Formalizing Theoretical Domains

in715_deficit_proper_row_12

theoremverified

Finite certificate for the explicit fourteen-vertex graph.

Statement

theorem in715_deficit_proper_row_12 : ∀ v : Fin 14, G.Adj 12 v → s((12 : Fin 14),v) ∉ C → color 12 ≠ color v
Source
Finite graph and certificates from experiments 20940 and 20968; see state/campaigns/triangle_reductions/outside_induced_kernel_in701.md.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

To verify that any edge incident to vertex 12 outside the deficit set $C$ is properly colored, the proof reduces the universal quantifier to finite case exhaustion over all 14 vertices. Because the graph, the deficit set, and the vertex coloring are all explicitly defined finite combinatorial objects, the kernel decides each of the 14 cases by direct boolean computation.

  1. Fix an arbitrary vertex $v$ in the graph.

    We introduce the vertex variable $v$, reducing the universal statement to showing that if $v$ is adjacent to vertex 12 and the undirected edge $\{12, v\}$ does not belong to the deficit set $C$, then vertex 12 and vertex $v$ have different colors.

    line 7

      intro v
  2. The condition holds for all 14 choices of vertex $v$. automation

    We exhaust all 14 possible values of $v \in \mathrm{Fin}\ 14$. Because the graph adjacency relation $G$, the deficit edge set $C$, and the vertex coloring are all explicitly defined finite data structures, each case reduces to a closed decidable proposition. The Lean kernel computes the truth value of each case directly and confirms it holds.

    line 8

      fin_cases v <;> decide +kernel

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

open scoped Sym2set_option maxRecDepth 100000set_option maxHeartbeats 30000000open In701Deficit14theorem in715_deficit_proper_row_12 : ∀ v : Fin 14, G.Adj 12 v → s((12 : Fin 14),v) ∉ C → color 12 ≠ color v := by  intro v  fin_cases v <;> decide +kernel
See it in the graphDiscuss this resultChallenge it