AFTD Auto-Formalizing Theoretical Domains

poc8_graph

def

The 8-vertex graph G with edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67.

Statement

def poc8_graph : SimpleGraph (Fin 8)
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 7
  • poc8_cutb_soundIf the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.
  • poc8_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.
  • poc_linkedness_conjecture_counterexampleCounterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not…
  • 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_connb_soundIf the Boolean connectivity test accepts S, then S induces a connected subgraph of G.
  • poc8_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.
  • 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.

Lean source view module on GitHub

/-- The 8-vertex counterexample graph. -/
def poc8_graph : SimpleGraph (Fin 8) :=
  { Adj := fun a b => poc8_adj a b = true
    symm := ⟨by decide⟩
    loopless := ⟨by decide⟩ }
See it in the graphDiscuss this resultChallenge it