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

4$\begingroup$ Freddy Barrera has verified that G(194) is the first time G(n) has diameter 4. He conjectures that the diameter is 4 for all n > 328. $\endgroup$ – Bernardo Recamán Santos Apr 4 '15 at 2:08

1$\begingroup$ Do you know any argument showing that the diameter can't be 3 for sufficiently large $n$? $\endgroup$ – Anthony Quas Apr 4 '15 at 6:50

1$\begingroup$ For all n from 329 to 7000 the diameter is 4. Further, the eccentricity of vertex n in G(n) is 4 for all n from 243 to 7000. $\endgroup$ – user48028 Apr 4 '15 at 7:36

1$\begingroup$ I wonder how large the clique number of this graph gets? The first K4 I see is at n=6724 (the vertices are 2, 167, 674, and 6722). There may be smaller ones. $\endgroup$ – user48028 Apr 4 '15 at 9:17

1$\begingroup$ Finding such cliques is problem D15 in Richard Guy´s Unsolved Problems in Number Theory (3rd edition). Many examples are known of K4. Stan Wagon apparently found examples of K5. $\endgroup$ – Bernardo Recamán Santos Apr 4 '15 at 13:36
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)(ed). 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.

$\begingroup$ Wouldn't this prove that the diameter is $3$ when it works? $\endgroup$ – Christian Remling Apr 4 '15 at 15:24

$\begingroup$ I count diameter as length of a path from endtoend, counted by vertices. But I am not a graph theorist. Also, this just shows small diameter for a small initial section of the graph. However, one more step from b may reach the rest of the graph. $\endgroup$ – The Masked Avenger Apr 4 '15 at 15:30
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]^2c<2\sqrt n+1.$ So we need one step to $M$, two steps inside $M$, and one step from $M$.

$\begingroup$ Pitifully, $a$ and $a+1$ are never at distance 2. $\endgroup$ – Ilya Bogdanov Apr 5 '15 at 10:22

$\begingroup$ @Ilya Bogdanov Because we work with positive integers. $\endgroup$ – Alexey Ustinov Apr 5 '15 at 10:24
(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 lowerright 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$.