2026/08/03 by Randy Davila
Mathematics · #math.CO
arxiv created 2026/08/03 · arxiv updated 2026/08/06
For an integer n≥2, let Gn be the graph on \2,…,n\ in which distinct integers are adjacent when they have a nontrivial common divisor. Conjecture 448 of Fajtlowicz's Written on the Wall asked for a lower bound on the Havel--Hakimi residue \R(Gn). The accompanying historical notes record a stronger lower bound of Erdős and Staton and Staton's conjecture that \(\R(Gn)∼(ζ(2)-1)n/log n\). We prove this conjecture and determine the next asymptotic term. If A=∑k=2∞(log k)/(k2(k-1)) =0.3201986326…, then \R(Gn)= (ζ(2)-1)(n)/(log n) +(ζ(2)-1-A)(n)/(log2 n) +O ((n)/(log3 n)). The lower estimate comes from an exact analysis of the Caro--Wei mass of the prime vertices. For the upper estimate, we construct another realization of the degree sequence of Gn: almost every bounded-degree prime vertex is placed in a clique of the order forced by its degree, while degree-preserving switches are absorbed by composite cliques. The proof gives a rare meeting point between prime number asymptotics, degree-sequence algorithms, and automated conjecturing. It also provides a traceable case study in which Theo-Conjecture, an advisor-supervised AI loop, converts registry experiments and counterexamples into a rigorous theorem. We also give an exact Havel--Hakimi defect decomposition. Computation suggests the substantially stronger bound \( \R(Gn)≤\lceil\CW(Gn)\rceil+2, \) which we state as an open Theo-Conjecture problem.