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