AFTD Auto-Formalizing Theoretical Domains

poc8_connb

def

Boolean connectivity test: some vertex r of S reaches every vertex of S within 7 BFS steps inside S.

Statement

def poc8_connb (S : Fin 8 → Bool) : Bool
Source
step towards poc_linkedness_conjecture_counterexample (counterexample to arXiv:1908.05433, Conjecture 3.10; kernel-checked certificate)
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • poc8_closek breadth-first-search steps inside S starting from R.
Used by 2
  • poc8_cands_connEach of the 47 stored masks and its complement pass the Boolean connectivity test (kernel computation).
  • poc8_connb_soundIf the Boolean connectivity test accepts S, then S induces a connected subgraph of G.

Lean source view module on GitHub

/-- Boolean test: some `r ∈ S` reaches all of `S` in 7 BFS steps inside `S`. -/
def poc8_connb (S : Fin 8 → Bool) : Bool :=
  (List.finRange 8).any fun r =>
    S r && (List.finRange 8).all fun v => !S v || poc8_close S (fun w => w == r) 7 v
See it in the graphDiscuss this resultChallenge it