(Not an answer; just a comment.)

It is a somewhat tangled graph. Here is a representation of $G(100)$:
<hr />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
![SqGraph100][1]
<hr />
One can see $50+71=121=11^2$ near the lower-right corner,
$84+85=169=13^2$ near the top,
$82+62=144=12^2$, near the bottom, etc.

This $G(100)$ graph has diameter $5$. But $G(1000)$ has diameter $4$.


  [1]: https://i.sstatic.net/Bnt6h.jpg