Let $\mathbb{N}$ denote the set of positive integers, and consider the graph $(\mathbb{N}, E)$ where a set $\{a,b\}$ of two distinct positive integers belongs to $E$ if there is an integer $k>1$ such that $a = k\cdot b$ or $b = k \cdot a$.


**Questions.**


1. Is there a bijection $p:\mathbb{N}\to\mathbb{N}$ such that for all $k\in \mathbb{N}$ we have $\{p(k), p(k+1)\} \in E$?
2. Is there a bijection $p:\mathbb{Z}\to\mathbb{N}$ such that for all $k\in \mathbb{Z}$ we have $\{p(k), p(k+1)\} \in E$?



Hamiltonian path in divisibility graph
Yes, as for every countable graph on which any two vertices have infinitely many common neighbours. If you constructed a path $v\_1\ldots v\_m$, and $u$ is the first (with respect to a numeration chosen in advance) not visited vertex, then you may proceed with $\dots v\_{m+1}u$, where $v\_{m+1}$ is a not used yet common neighbour of $v\_m$ and $u$.


