finite_cubic_ten_connector_count_and_forced_edge
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.
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`.
set_option maxRecDepth 100000 in set_option maxHeartbeats 0 in decide
- The proof contains no manual deductive steps; it relies entirely on Lean evaluating the decidable proposition over all 2¹⁰ = 1024 vertex subsets.
- The options `maxRecDepth 100000` and `maxHeartbeats 0` are compiler directives that raise the recursion limit and disable the timeout counter so that the exhaustive evaluation can finish.
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.
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