AFTD Auto-Formalizing Theoretical Domains

in715_deficit_proper_row_8

theoremverified

Finite certificate for the explicit fourteen-vertex graph.

Statement

theorem in715_deficit_proper_row_8 : ∀ v : Fin 14, G.Adj 8 v → s((8 : Fin 14),v) ∉ C → color 8 ≠ 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 vertex coloring on the 14-vertex graph $G$ is proper along all edges incident to vertex 8, with the possible exception of edges in the cut set $C$. The proof introduces an arbitrary vertex $v$ and performs an exhaustive case analysis across all 14 vertices. Each individual case is closed by direct computation in Lean's kernel, evaluating the finite adjacency relation, set membership, and color assignment.

  1. Let $v$ be an arbitrary vertex in the 14-vertex graph.

    We introduce the vertex $v \in \mathrm{Fin}\;14$ for the universal quantifier.

    line 7

      intro v
  2. For every vertex $v$, if $v$ is adjacent to 8 and the edge $\{8, v\}$ does not belong to $C$, then vertex 8 and vertex $v$ receive distinct colors. automation

    Because $\mathrm{Fin}\;14$ has only fourteen elements, the proof splits into fourteen cases ($v = 0, 1, \dots, 13$). For each concrete value of $v$, the graph adjacency, edge membership in $C$, and vertex colors are fully concrete, so each resulting implication is verified by direct kernel computation (`decide +kernel`).

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