AFTD Auto-Formalizing Theoretical Domains

poc8_close

def

k breadth-first-search steps inside S starting from R.

Statement

def poc8_close (S R : Fin 8 → Bool) (k : ℕ) : Fin 8 → 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_stepOne breadth-first-search step inside S: add to R every vertex of S adjacent to a vertex of R.
Used by 3
  • poc8_close_soundEvery vertex reached by the BFS iteration from r inside S lies in S and is reachable from r in the subgraph induced by S.
  • poc8_connbBoolean connectivity test: some vertex r of S reaches every vertex of S within 7 BFS steps inside S.
  • poc8_discbBoolean disconnectedness test: S is empty, or the BFS closure inside S of some vertex of S is a proper cut of S.

Lean source view module on GitHub

/-- `k` iterated BFS steps inside `S` from `R`. -/
def poc8_close (S R : Fin 8 → Bool) (k : ℕ) : Fin 8 → Bool :=
  match k with
  | 0 => R
  | k + 1 => poc8_step S (poc8_close S R k)
See it in the graphDiscuss this resultChallenge it