AFTD Auto-Formalizing Theoretical Domains

in715_deficit_p_tri

theoremverified

Finite certificate for the explicit fourteen-vertex graph.

Statement

theorem in715_deficit_p_tri : ∀ t ∈ P, G.IsNClique 3 t
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
Used by 2
  • in715_deficit_preciseAn explicit fourteen-vertex graph has a maximum seven-triangle packing, a seven-edge triangle cover, an outside five-cycle link and a…
  • in715_deficit_pack_eqFinite certificate for the explicit fourteen-vertex graph.

The proof, explained

The theorem asserts that every set $t$ in the family $P$ forms a 3-clique (triangle) in the 14-vertex graph $G$. The proof unfolds the definition of the finite family $P$ into seven explicit 3-element candidate sets and verifies each one by exhaustive finite computation.

  1. Let $t$ be an arbitrary element of $P$.

    We fix a candidate subset $t$ and assume the hypothesis $t \in P$.

    line 7

      intro t ht
  2. $t$ must be one of the seven explicitly enumerated candidate triangles: $\{0, 1, 5\}$, $\{1, 2, 6\}$, $\{2, 3, 7\}$, $\{3, 4, 8\}$, $\{0, 4, 9\}$, $\{0, 11, 12\}$, or $\{1, 11, 13\}$.

    Unfolding the definition of $P$ and simplifying set membership using the characterizations of membership in an inserted set and a singleton set expands $t \in P$ into a 7-way disjunction.

    line 8

    uses P, Finset.mem_insert, Finset.mem_singleton

      simp only [P, Finset.mem_insert, Finset.mem_singleton] at ht
  3. In each of the seven cases, $t$ is indeed a 3-clique in $G$. automation

    We case-split across the seven disjuncts, substituting the explicit vertex set into the goal in each case, and verify by direct kernel computation that the three vertices are pairwise adjacent in $G$.

    line 9

      rcases ht with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> decide +kernel
Finset.mem_insert
An element `a` belongs to `insert b s` if and only if `a = b` or `a ∈ s`.
Finset.mem_singleton
An element `b` belongs to the singleton `{a}` if and only if `b = a`.
P
The explicit collection of seven 3-element subsets of vertices in the 14-vertex graph.

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_p_tri : ∀ t ∈ P, G.IsNClique 3 t := by  intro t ht  simp only [P, Finset.mem_insert, Finset.mem_singleton] at ht  rcases ht with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> decide +kernel
See it in the graphDiscuss this resultChallenge it