in715_deficit_proper
Finite certificate for the explicit fourteen-vertex graph.
Statement
theorem in715_deficit_proper : ∀ u v : Fin 14, G.Adj u v → s(u,v) ∉ C → color u ≠ 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 15
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_0Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_1Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_2Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_3Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_4Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_5Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_6Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_7Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_8Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_9Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_10Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_11Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_12Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_13Finite certificate for the explicit fourteen-vertex graph.
- Used by 1
- in715_deficit_coverFinite certificate for the explicit fourteen-vertex graph.
The proof, explained
The theorem asserts that the vertex coloring on the 14-vertex graph G is proper on all edges outside the set C. The proof introduces an arbitrary vertex u, performs an exhaustive case analysis over the 14 vertices in Fin 14, and completes each case using a precomputed certificate lemma for that row.
It suffices to check the property for each vertex u ∈ {0, 1, …, 13}.
Introduce the vertex u and split into 14 cases corresponding to each element of Fin 14.
intro u fin_cases uFor every pair of adjacent vertices u, v whose connecting edge is not in C, color u ≠ color v.
Discharge each of the 14 cases by applying the corresponding precomputed row certificate lemma.
uses
in715_deficit_proper_row_0,in715_deficit_proper_row_1,in715_deficit_proper_row_2,in715_deficit_proper_row_3,in715_deficit_proper_row_4,in715_deficit_proper_row_5,in715_deficit_proper_row_6,in715_deficit_proper_row_7,in715_deficit_proper_row_8,in715_deficit_proper_row_9,in715_deficit_proper_row_10,in715_deficit_proper_row_11,in715_deficit_proper_row_12,in715_deficit_proper_row_13· exact in715_deficit_proper_row_0 · exact in715_deficit_proper_row_1 · exact in715_deficit_proper_row_2 · exact in715_deficit_proper_row_3 · exact in715_deficit_proper_row_4 · exact in715_deficit_proper_row_5 · exact in715_deficit_proper_row_6 · exact in715_deficit_proper_row_7 · exact in715_deficit_proper_row_8 · exact in715_deficit_proper_row_9 · exact in715_deficit_proper_row_10 · exact in715_deficit_proper_row_11 · exact in715_deficit_proper_row_12 · exact in715_deficit_proper_row_13
in715_deficit_proper_row_0- For any vertex v adjacent to 0 in G, if the edge {0, v} is not in C, then 0 and v have distinct colors.
in715_deficit_proper_row_1- For any vertex v adjacent to 1 in G, if the edge {1, v} is not in C, then 1 and v have distinct colors.
in715_deficit_proper_row_2- For any vertex v adjacent to 2 in G, if the edge {2, v} is not in C, then 2 and v have distinct colors.
in715_deficit_proper_row_3- For any vertex v adjacent to 3 in G, if the edge {3, v} is not in C, then 3 and v have distinct colors.
in715_deficit_proper_row_4- For any vertex v adjacent to 4 in G, if the edge {4, v} is not in C, then 4 and v have distinct colors.
in715_deficit_proper_row_5- For any vertex v adjacent to 5 in G, if the edge {5, v} is not in C, then 5 and v have distinct colors.
in715_deficit_proper_row_6- For any vertex v adjacent to 6 in G, if the edge {6, v} is not in C, then 6 and v have distinct colors.
in715_deficit_proper_row_7- For any vertex v adjacent to 7 in G, if the edge {7, v} is not in C, then 7 and v have distinct colors.
in715_deficit_proper_row_8- For any vertex v adjacent to 8 in G, if the edge {8, v} is not in C, then 8 and v have distinct colors.
in715_deficit_proper_row_9- For any vertex v adjacent to 9 in G, if the edge {9, v} is not in C, then 9 and v have distinct colors.
in715_deficit_proper_row_10- For any vertex v adjacent to 10 in G, if the edge {10, v} is not in C, then 10 and v have distinct colors.
in715_deficit_proper_row_11- For any vertex v adjacent to 11 in G, if the edge {11, v} is not in C, then 11 and v have distinct colors.
in715_deficit_proper_row_12- For any vertex v adjacent to 12 in G, if the edge {12, v} is not in C, then 12 and v have distinct colors.
in715_deficit_proper_row_13- For any vertex v adjacent to 13 in G, if the edge {13, v} is not in C, then 13 and v have distinct colors.
- The checks for each vertex row are precomputed as separate lemmas (`in715_deficit_proper_row_0` through `in715_deficit_proper_row_13`), which verify the color distinction for all neighbors of that specific vertex.
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 : ∀ u v : Fin 14, G.Adj u v → s(u,v) ∉ C → color u ≠ color v := by intro u fin_cases u · exact in715_deficit_proper_row_0 · exact in715_deficit_proper_row_1 · exact in715_deficit_proper_row_2 · exact in715_deficit_proper_row_3 · exact in715_deficit_proper_row_4 · exact in715_deficit_proper_row_5 · exact in715_deficit_proper_row_6 · exact in715_deficit_proper_row_7 · exact in715_deficit_proper_row_8 · exact in715_deficit_proper_row_9 · exact in715_deficit_proper_row_10 · exact in715_deficit_proper_row_11 · exact in715_deficit_proper_row_12 · exact in715_deficit_proper_row_13