(Not an answer; just a comment.)
It is a somewhat tangled graph. Here is a representation of $G(100)$:
![SqGraph100][1]
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$.