A Logarithmic Upper Bound for Diameters of Finite Diophantine Graphs

Let $G_N$ be a graph on vertex set $\{1, \dots, N\}$ where two distinct vertices $a$ and $b$ share an edge if $ab+1$ is a square. We prove that $G_N$ is connected for all $N \ge 8$ and provide the explicit upper bound $\text{diam}(G_N) \le 26\lceil\log_{16}(\frac{N}{18})\rceil + 16$ by constructing explicit paths to a fixed finite subgraph.