Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure

Abstract

Let $G_n$ be the graph on $\{2,\dots ,n\}$ in which two integers are adjacent when they have a common divisor greater than one. We determine the complete asymptotic expansion of its Havel--Hakimi residue $\mathbb{R}(G_n)$, confirming a leading-constant prediction of Staton recorded in Fajtlowicz's \emph{Written on the Wall}. If $A={\sum }_{k=2}^{\infty }(\log k)/(k^2(k-1))$, then the first two terms are $\mathbb{R}(G_n)=(\zeta (2)-1)n/\log n+(\zeta (2)-1-A)n/{\log }^{2}n+O(n/{\log }^{3}n)$. More precisely, the difference between $\mathbb{R}(G_n)$ and the prime-vertex contribution to the Caro--Wei sum is $O_{\beta }(n\exp \{-(\log n{)}^{\beta }\})$ for every fixed $0<\beta <1/2$; this estimate yields every coefficient in the expansion. The upper bound follows from a degree-preserving realization in which almost all relevant prime vertices are partitioned into cliques. We also prove that the unlabeled graph determines $\pi (n)$ through its simplicial true-twin classes. Stable inverses for weighted sums of the resulting degree-class counts give criteria equivalent to the Riemann hypothesis, including one involving only the Caro--Wei sum. An exact local-defect identity additionally reduces the conjectured sharp $+2$ residue bound to explicit prefix estimates.