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

• 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. – Bernardo Recamán Santos Apr 4 '15 at 2:08
• Do you know any argument showing that the diameter can't be 3 for sufficiently large $n$? – Anthony Quas Apr 4 '15 at 6:50
• 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. – user48028 Apr 4 '15 at 7:36
• 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. – user48028 Apr 4 '15 at 9:17
• 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. – 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)(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.

• Wouldn't this prove that the diameter is $3$ when it works? – Christian Remling Apr 4 '15 at 15:24
• I count diameter as length of a path from end-to-end, 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. – 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]^2-c|<2\sqrt n+1.$ So we need one step to $M$, two steps inside $M$, and one step from $M$.

• Pitifully, $a$ and $a+1$ are never at distance 2. – Ilya Bogdanov Apr 5 '15 at 10:22
• @Ilya Bogdanov Because we work with positive integers. – 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 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$.