in715_deficit_proper_row_1
Finite certificate for the explicit fourteen-vertex graph.
Statement
theorem in715_deficit_proper_row_1 : ∀ v : Fin 14, G.Adj 1 v → s((1 : Fin 14),v) ∉ C → color 1 ≠ 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
The theorem verifies that vertex 1 satisfies the proper coloring condition with respect to all of its neighbors outside of $C$ in an explicit 14-vertex graph. The proof performs an exhaustive case analysis across all 14 possible vertices $v \in \mathrm{Fin}\ 14$. For each vertex, the condition is a decidable proposition on finite data and is discharged directly by kernel evaluation.
Let $v$ be an arbitrary vertex in the 14-vertex graph.
We introduce the universally quantified vertex $v \in \mathrm{Fin}\ 14$ to prove the implication for any chosen vertex.
intro vFor every concrete vertex $v \in \{0, \dots, 13\}$, if vertex 1 is adjacent to $v$ and the edge $\{1, v\}$ is not in $C$, then vertex 1 and vertex $v$ have different colors. automation
The tactic `fin_cases v` enumerates all 14 possible values of $v \in \mathrm{Fin}\ 14$. For each concrete vertex, the adjacency relation $G.\mathrm{Adj}\ 1\ v$, the edge non-membership $s(1, v) \notin C$, and the color inequality $\mathrm{color}\ 1 \neq \mathrm{color}\ v$ are decidable finite propositions. The `decide +kernel` tactic evaluates each case directly within Lean's kernel by computing the explicit boolean values, closing all 14 goals.
fin_cases v <;> decide +kernel
- The fourteen subgoals generated by exhaustive case analysis are resolved entirely by Lean's kernel evaluator (`decide +kernel`), which computes the finite graph adjacencies, edge set membership, and vertex colors directly from their definitions.
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_1 : ∀ v : Fin 14, G.Adj 1 v → s((1 : Fin 14),v) ∉ C → color 1 ≠ color v := by intro v fin_cases v <;> decide +kernel