AFTD Auto-Formalizing Theoretical Domains

poc8_discb

def

Boolean disconnectedness test: S is empty, or the BFS closure inside S of some vertex of S is a proper cut of S.

Statement

def poc8_discb (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 2
  • poc8_closek breadth-first-search steps inside S starting from R.
  • poc8_cutbBoolean cut test: R is nonempty, R ⊆ S, S ⊄ R, and no edge leads from R to a vertex of S outside R.
Used by 2
  • poc8_gmms_okCheck for a bipartition (P, not P): 8 times the smaller part value is below 105 = 7·15, or one of the two parts is disconnected.
  • poc8_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.

Lean source view module on GitHub

/-- Boolean test: `S` is empty or the BFS closure of some vertex of `S` is a proper cut of `S`. -/
def poc8_discb (S : Fin 8 → Bool) : Bool :=
  (List.finRange 8).all (fun v => !S v) ||
    (List.finRange 8).any fun r => S r && poc8_cutb S (poc8_close S (fun w => w == r) 7)
See it in the graphDiscuss this resultChallenge it