AFTD Auto-Formalizing Theoretical Domains

op_193_disjoint_anchor_packings

theoremverified

The thirteen-cycle has nine stable triples and the fourteen-cycle has ten stable triples, respectively, with any two triples sharing at most one vertex.

Statement

theorem op_193_disjoint_anchor_packings :
    (∃ A : Fin 9 → Finset (Fin 13),
      (∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 13).IsIndepSet (↑(A j) : Set (Fin 13))) ∧
      ∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1) ∧
    (∃ A : Fin 10 → Finset (Fin 14),
      (∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 14).IsIndepSet (↑(A j) : Set (Fin 14))) ∧
      ∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1)
Source
Finite obstructions to overlap-only improvements of the anchor edge count; experiment 23383.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by exhibiting explicit witness families of triples for both cycle graphs. For the 13-cycle, an explicit collection of 9 triples (`in777_pack13`) is provided, and for the 14-cycle, an explicit collection of 10 triples (`in777_pack14`) is provided. In both cases, the three conditions—each triple has size three, each triple is an independent set in the cycle, and any two triples intersect in at most one vertex—are verified by finite exhaustive computation using `decide`.

  1. Both the 13-cycle and the 14-cycle admit the required collections of independent triples with pairwise intersection of size at most 1. automation

    The proof provides explicit witness families: `in777_pack13` (9 triples in the 13-cycle) and `in777_pack14` (10 triples in the 14-cycle). Because all the sets are finite and the cycle graphs are finite, verifying that each triple has size 3, forms an independent set (contains no two vertices adjacent in the cycle), and shares at most one vertex with any distinct triple is a finite boolean decision problem closed by exhaustive computation (`decide`).

    line 15

      exact ⟨⟨in777_pack13, by decide⟩, ⟨in777_pack14, by 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

set_option maxRecDepth 100000set_option maxHeartbeats 2000000private def in777_pack13 : Fin 9 → Finset (Fin 13) := ![{0,3,6}, {0,8,10}, {0,9,11}, {1,6,9}, {1,7,11}, {2,4,8}, {2,6,12}, {2,7,10}, {5,9,12}]private def in777_pack14 : Fin 10 → Finset (Fin 14) := ![{0,3,7}, {0,8,10}, {1,3,5}, {1,10,13}, {2,4,12}, {2,5,8}, {2,6,11}, {2,9,13}, {3,6,10}, {6,8,13}]theorem op_193_disjoint_anchor_packings :    (∃ A : Fin 9 → Finset (Fin 13),      (∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 13).IsIndepSet (↑(A j) : Set (Fin 13))) ∧      ∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1) ∧    (∃ A : Fin 10 → Finset (Fin 14),      (∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 14).IsIndepSet (↑(A j) : Set (Fin 14))) ∧      ∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1) := by  exact ⟨⟨in777_pack13, by decide⟩, ⟨in777_pack14, by decide⟩⟩
See it in the graphDiscuss this resultChallenge it