The diameter of a certain graph on the positive integers Let $G(n)$ be the graph whose vertices are the positive integers $1,2,3,4, \ldots, n$  two of which are joined by an edge if their sum is a square. Is the diameter of this graph 4 for all sufficiently large $n$?
 A: Maybe this will work.
Given positive integers a and b, choose c large enough so that c^2 > a+b.
also, choose c so that c^2 -a -b is odd and factors as (e+d)(e-d).
Then a has an edge with c^2 - a, b has an edge with d^2 - b, and
c^2 - a -b + d^2 = e^2.  So choose c also so that c^2 - a is distinct from
a and from d^2 - b.  I leave the existence of c to others.
A: Probably this idea can confirm the conjecture.
There are a lot of couples $(a,b)$ such that $a+b$ is odd, $a<b$ and $\mathrm{Dist}(a,b)\le 2$. We can try to find $x\le n$ such that
$$a+x=y^2\quad\text{ and }\quad b+x=(y+1)^2.$$ So $1$ is connected (connection length is $2$) with $6$, $8$, $\ldots$ $2[\sqrt{n+1}]$, $2$ is connected with $7$, $9$, $\ldots$ $2[\sqrt{n+2}]$, etc. This first step gives highly connected component $M$ inside $[1,2\sqrt n]$. A big number $2\sqrt n<c\le n$  we can try to connect with $M$ considering the nearest square $[\sqrt c]^2$ because $|[\sqrt c]^2-c|<2\sqrt n+1.$ So we need one step to $M$, two steps inside $M$, and one step from $M$.
A: (Not an answer; just a comment.)
It is a somewhat tangled graph. Here is a representation of $G(100)$:

         


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$.
