I found the following abstract which is relevant to the question of the existence of a Hamiltonian path in an infinite graph: --------------------------------------------------------------------- 46 #94 Nash-Williams, C. St. J. A. Hamiltonian lines in infinite graphs with few vertices of small valency. Aequationes Math. 7 (1971), 59--81. 05C35 -------------------------------------------------------------------------------- A graph $G$ is said to be $r$-divisible if there is a finite set $X$ of its vertices such that $G-X$ has at least $r$ infinite components. The two main results of this paper go as follows. Let $G$ be a graph with vertex-set $A\cup\{u_1,u_2,\cdots\}$ where $A$ is finite and $u_1,u_2,\cdots$ are distinct; suppose that each $u_i$ has valency $\geq i [\geq i+1]$ and that every vertex in $A$ has infinite valency; then $G$ has a one-way [two-way] infinite Hamiltonian arc if and only if it is not 2-divisible [connected and no 3-divisible]. These two theorems represent infinite versions of L. Psa's theorem [Magyar Tud. Akad. Mat. Kutat Int. Kzl. 7 (1962), 225--226; MR 32 #2347]. However, their proof is much more complicated and involves a total of 38 lemmas. The author remarks that the (clearly necessary) divisibility conditions were suggested by an earlier work of Erds, Gallai and Vszonyi on Euler paths in infinite graphs. He also shows, by means of a counterexample that the valency conditions cannot be weakened in any obvious way. The valency conditions in the one-way theorem together with 2-indivisibility imply that $G$ is connected. This fails to be true in the two-way case; hence the apparent symmetry flaw. The author asks whether every $(i+1)$-indivisible 4-connected denumerable planar graph has an $i$-way infinite Hamiltonian arc. The positive answer would represent an infinite version of W. T. Tutte's theorem [Trans. Amer. Math. Soc. 82 (1956), 99--116; MR 18, 408]. He also poses two other unsolved problems; a study of these might lead to a simplification of the present proofs. ------------------------------------------------------------------------- If we apply this to the case of the "square" graph on N, since every vertex has infinite valency to prove that the graph has a Hamiltonian path it seems (if I follow Nash-Williams' result) that we ONLY need to prove that one cannot disconnect the graph into two or more infinite components by removing a finite number of vertices. This would apply equally to the "primes", "fibonacci", etc...(if S is any infinite subset of N and adjacency is defined by i + j \in S). Edwin