in715_deficit_proper_row_10
Finite certificate for the explicit fourteen-vertex graph.
Statement
theorem in715_deficit_proper_row_10 : ∀ v : Fin 14, G.Adj 10 v → s((10 : Fin 14),v) ∉ C → color 10 ≠ 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 asserts that the vertex coloring is proper on all edges incident to vertex 10, except possibly those in the specified deficit set $C$. Since the graph has only fourteen vertices, the proof exhaustively tests each of the 14 possibilities for the neighbor $v$ by direct kernel computation.
Let $v$ be an arbitrary vertex of the graph.
We introduce the universally quantified variable $v \\in \\mathrm{Fin}\\,14$. It remains to show that if $v$ is adjacent to 10 and the edge $\{10, v\}$ is not in the deficit set $C$, then $v$ and 10 receive distinct colors.
intro vFor every vertex $v \\in \\mathrm{Fin}\\,14$, if $v$ is adjacent to 10 in $G$ and the edge $s(10, v) \\notin C$, then $\\mathrm{color}(10) \\neq \\mathrm{color}(v)$. automation
Because $v$ belongs to the finite set $\{0, 1, \\dots, 13\}$, the proof performs an exhaustive case analysis across all 14 possible vertices. For each concrete vertex, the adjacency relation, membership of the unordered pair in $C$, and the color values are explicit finite data, so each case is verified by direct computational evaluation in the kernel.
fin_cases v <;> decide +kernel
- The proof delegates all case verification to Lean's kernel (`decide +kernel`), which evaluates the finite combinatorial properties (graph adjacency, set non-membership, and inequality of colors) by direct computation.
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_10 : ∀ v : Fin 14, G.Adj 10 v → s((10 : Fin 14),v) ∉ C → color 10 ≠ color v := by intro v fin_cases v <;> decide +kernel