SAUDI ARABIAN MATHEMATICAL COMPETITIONS

If $x,y\in {\mathbb{Z}}^{+}$, define $x\leftrightarrow y$ if and only if $x,y$ are connected by some edge. We have for all $a\in {\mathbb{Z}}^{+}$, $$a^2+a+1\mid (a^2-a+1)(a^2+a+1)=a^4+a^2+1.$$ Thus $a\leftrightarrow a^2$ for all $a$, then also true for $a+1\leftrightarrow (a+1{)}^2$. Moreover, $$\begin{array}{rl}{\left(a^2\right)}^2+{\left((a+1{)}^2\right)}^2+1& =2a^4+4a^3+6a^2+4a+2\\ & =\left(2a^2+2a+2\right)\left(a^2+a+1\right)\end{array}$$ Thus $a^2+(a+1{)}^2+1=2a^2+2a+2$ divides ${\left(a^2\right)}^2+{\left((a+1{)}^2\right)}^2+1$, which implies that $a^2\leftrightarrow (a+1{)}^2$. Hence, $$a\leftrightarrow a^2\leftrightarrow (a+1{)}^2\leftrightarrow a+1,$$ this means that every two consecutive integers $a,a+1$ are connected. Thus the given infinity graph is connected. $\square$