AFTD Auto-Formalizing Theoretical Domains

in715_deficit_proper_row_0

theoremverified

Finite certificate for the explicit fourteen-vertex graph.

Statement

theorem in715_deficit_proper_row_0 : ∀ v : Fin 14, G.Adj 0 v → s((0 : Fin 14),v) ∉ C → color 0 ≠ 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

The theorem establishes that the coloring on the 14-vertex graph is proper along any edge incident to vertex 0, outside of an exceptional deficit set $C$. The proof proceeds by finite case exhaustion over all vertices $v \in \{0, \dots, 13\}$. For each of the 14 vertices, the statement is a decidable proposition on explicit finite structures, which is closed by computational evaluation in Lean's kernel.

  1. It suffices to establish the property for an arbitrary vertex $v$.

    Fix an arbitrary vertex $v \in \{0, \dots, 13\}$ in the 14-vertex graph.

    line 7

      intro v
  2. The implication holds for all 14 possible vertices $v$. automation

    Since the vertex type is $\mathrm{Fin}\; 14$, `fin_cases v` splits the goal into 14 concrete cases, one for each vertex $0 \le v < 14$. In each branch, the adjacency of $0$ and $v$ in $G$, the membership of $\{0, v\}$ in the deficit set $C$, and the values $\mathrm{color}(0)$ and $\mathrm{color}(v)$ are completely explicit and decidable; `decide +kernel` computes and evaluates each proposition directly to verify the implication.

    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_0 : ∀ v : Fin 14, G.Adj 0 v → s((0 : Fin 14),v) ∉ C → color 0 ≠ color v := by  intro v  fin_cases v <;> decide +kernel
See it in the graphDiscuss this resultChallenge it