AFTD Auto-Formalizing Theoretical Domains

in715_deficit_link_is_cycle

theoremverified

Finite certificate for the explicit fourteen-vertex graph.

Statement

theorem in715_deficit_link_is_cycle : ∀ u v : Fin 14,
    u ∈ ({0,1,2,3,4} : Finset (Fin 14)) →
    v ∈ ({0,1,2,3,4} : Finset (Fin 14)) →
    (In701Deficit14.G.Adj u v ↔ s(u,v) ∈
      ({s(0,1),s(1,2),s(2,3),s(3,4),s(0,4)} : Finset (Sym2 (Fin 14))))
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 1
  • 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…

The proof, explained

The theorem establishes that in the explicit 14-vertex graph `In701Deficit14.G`, the subgraph induced on the subset of vertices $\{0, 1, 2, 3, 4\}$ is a 5-cycle with edges $\{0, 1\}, \{1, 2\}, \{2, 3\}, \{3, 4\}$, and $\{0, 4\}$. Because the vertex set is finite and the graph's adjacency relation is explicitly computable, the proposition is decidable. The proof executes this finite verification directly via computation in the Lean kernel.

  1. For every pair of vertices $u, v \in \{0, 1, 2, 3, 4\}$, $u$ is adjacent to $v$ in `In701Deficit14.G` if and only if the unordered edge $\{u, v\}$ belongs to the 5-cycle edges $\{\{0, 1\}, \{1, 2\}, \{2, 3\}, \{3, 4\}, \{0, 4\}\}$. automation

    The vertex set is finite (`Fin 14`) and the graph's adjacency relation is fully explicit. The tactic `decide +kernel` evaluates this decidable proposition by exhaustively verifying the condition for all vertex pairs directly within Lean's computational kernel.

    line 10

      decide +kernel

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 30000000theorem in715_deficit_link_is_cycle : ∀ u v : Fin 14,    u ∈ ({0,1,2,3,4} : Finset (Fin 14)) →    v ∈ ({0,1,2,3,4} : Finset (Fin 14)) →    (In701Deficit14.G.Adj u v ↔ s(u,v) ∈      ({s(0,1),s(1,2),s(2,3),s(3,4),s(0,4)} : Finset (Sym2 (Fin 14)))) := by  decide +kernel
See it in the graphDiscuss this resultChallenge it