AFTD Auto-Formalizing Theoretical Domains

poc8_step

def

One breadth-first-search step inside S: add to R every vertex of S adjacent to a vertex of R.

Statement

def poc8_step (S R : Fin 8 → Bool) : 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_adjAdjacency of the 8-vertex graph with the 18 edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67, stored as…
Used by 2
  • 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_closek breadth-first-search steps inside S starting from R.

Lean source view module on GitHub

/-- One BFS step: `R` plus all vertices of `S` adjacent to `R`. -/
def poc8_step (S R : Fin 8 → Bool) : Fin 8 → Bool :=
  fun v => R v || (S v && (List.finRange 8).any fun w => R w && poc8_adj w v)
See it in the graphDiscuss this resultChallenge it