in715_deficit_proper_row_12
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
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
- Used by 1
- in715_deficit_properFinite certificate for the explicit fourteen-vertex graph.
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.
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.
intro vThe 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.
fin_cases v <;> decide +kernel
- The verification of all 14 cases is performed entirely through kernel computation (`decide +kernel`) evaluating finite graph data, rather than through manual deductive steps.
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.
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