A Logarithmic Upper Bound for Diameters of Finite Diophantine Graphs

Let GN be a graph on vertex set \1, , N\ where two distinct vertices a and b share an edge if $ab+1$ is a square. We prove that GN is connected for all N ≥ 8 and provide the explicit upper bound diam(GN) ≤ 26log₁₆(N/18) + 16 by constructing explicit paths to a fixed finite subgraph.