AFTD Auto-Formalizing Theoretical Domains

in715_deficit_proper

theoremverified

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
Used by 1

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.

  1. 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.

    lines 7–8

      intro u
      fin_cases u
  2. For 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.

    lines 9–22

    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.

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 : ∀ 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
See it in the graphDiscuss this resultChallenge it