AFTD Auto-Formalizing Theoretical Domains

poc8_cands_conn

theoremverified

Each of the 47 stored masks and its complement pass the Boolean connectivity test (kernel computation).

Statement

theorem poc8_cands_conn : ∀ m ∈ poc8_cands,
    poc8_connb (fun v => m.testBit v) = true ∧ poc8_connb (fun v => !m.testBit v) = true
Source
step towards poc_linkedness_conjecture_counterexample (counterexample to arXiv:1908.05433, Conjecture 3.10; kernel-checked certificate)
Verified
06 Oct 2026
Axioms
propext
Built on 2
  • poc8_cands47 vertex bitmasks, each the first part of a connected bipartition of G; together they separate every pair (M1, M2) of disjoint sets with…
  • poc8_connbBoolean connectivity test: some vertex r of S reaches every vertex of S within 7 BFS steps inside S.
Used by 1
  • poc8_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.

Lean source view module on GitHub

theorem poc8_cands_conn : ∀ m ∈ poc8_cands,    poc8_connb (fun v => m.testBit v) = true ∧ poc8_connb (fun v => !m.testBit v) = true := by  decide +kernel
See it in the graphDiscuss this resultChallenge it