AFTD Auto-Formalizing Theoretical Domains

poc8_adj

def

Adjacency 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 neighbourhood bitmasks.

Statement

def poc8_adj (a b : 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
Used by 5
  • poc8_graphThe 8-vertex graph G with edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67.
  • poc8_stepOne breadth-first-search step inside S: add to R every vertex of S adjacent to a vertex of R.
  • poc8_cutb_soundIf the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.
  • poc8_not_linked_two_fourG is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from…
  • poc8_cutbBoolean cut test: R is nonempty, R ⊆ S, S ⊄ R, and no edge leads from R to a vertex of S outside R.

Lean source view module on GitHub

/-- Adjacency of the 8-vertex counterexample graph (18 edges), as neighbourhood bitmasks. -/
def poc8_adj (a b : Fin 8) : Bool :=
  ((![240, 232, 216, 198, 165, 147, 143, 127] : Fin 8 → ℕ) a).testBit b
See it in the graphDiscuss this resultChallenge it