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{aligned} \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{aligned}$$
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$