poc8_cutb
def
Boolean cut test: R is nonempty, R ⊆ S, S ⊄ R, and no edge leads from R to a vertex of S outside R.
Statement
def poc8_cutb (S R : 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_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_cutb_soundIf the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.
- 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
/-- Boolean test that `R` is a proper nonempty part of `S` closed under edges inside `S`. -/ def poc8_cutb (S R : Fin 8 → Bool) : Bool := (List.finRange 8).any (fun v => R v) && (List.finRange 8).all (fun v => !R v || S v) && (List.finRange 8).any (fun v => S v && !R v) && (List.finRange 8).all (fun v => (List.finRange 8).all fun w => !S v || !R w || !poc8_adj w v || R v)