AFTD Auto-Formalizing Theoretical Domains

finite_cubic_ten_connector_count_and_forced_edge

theoremverified

For the specified fifteen-edge cubic graph and the designated root edge 01, any vertex subset S contains at most four more vertices than selected non-root edges; if equality holds and S does not contain both root endpoints then there is a non-root edge whose endpoints both lie outside S.

Statement

theorem finite_cubic_ten_connector_count_and_forced_edge :
    let E : Finset (Fin 10 × Fin 10) :=
      {(0,1),(0,4),(0,5),(1,2),(1,6),(2,3),(2,7),
       (3,4),(3,8),(4,9),(5,7),(5,8),(6,8),(6,9),(7,9)}
    let D := E.erase (0,1)
    ∀ S : Finset (Fin 10),
      let inside := D.filter (fun e => e.1 ∈ S ∧ e.2 ∈ S)
      S.card ≤ 4 + inside.card ∧
      (S.card = 4 + inside.card → (0 ∉ S ∨ 1 ∉ S) →
        ∃ e ∈ D, e.1 ∉ S ∧ e.2 ∉ S)
Source
Finite connector count underlying the 120-vertex packing-choice obstruction; experiments 17176 and 17181.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem asserts a vertex-edge count bound and a forced disjoint edge condition for every vertex subset in a specific 10-vertex cubic graph with one edge removed. Because the vertex set has only 10 elements, there are only 2¹⁰ = 1024 subsets in total, rendering the universal quantification over all subsets decidable. The proof proceeds by finite computational exhaustion, using Lean's `decide` tactic to evaluate and confirm the proposition for every subset.

  1. Both conditions—the cardinality bound |S| ≤ 4 + |inside| and the existence of an exterior edge when equality holds and {0, 1} ⊈ S—hold for all 1024 vertex subsets. automation

    The proposition is a bounded universal statement over the subsets of a 10-element finite set Fin 10. Because every operation (subset membership, filtering, and cardinality) is decidable, the entire statement is decidable by finite exhaustion over the 2¹⁰ = 1024 subsets. The `decide` tactic evaluates this boolean predicate directly to `true`.

    lines 11–13

      set_option maxRecDepth 100000 in
        set_option maxHeartbeats 0 in
          decide

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

theorem finite_cubic_ten_connector_count_and_forced_edge :    let E : Finset (Fin 10 × Fin 10) :=      {(0,1),(0,4),(0,5),(1,2),(1,6),(2,3),(2,7),       (3,4),(3,8),(4,9),(5,7),(5,8),(6,8),(6,9),(7,9)}    let D := E.erase (0,1)    ∀ S : Finset (Fin 10),      let inside := D.filter (fun e => e.1 ∈ S ∧ e.2 ∈ S)      S.card ≤ 4 + inside.card ∧      (S.card = 4 + inside.card → (0 ∉ S ∨ 1 ∉ S) →        ∃ e ∈ D, e.1 ∉ S ∧ e.2 ∉ S) := by  set_option maxRecDepth 100000 in    set_option maxHeartbeats 0 in      decide
See it in the graphDiscuss this resultChallenge it