Dan Hoey asks: << Now suppose we require Hamiltonian cycles for every {1,...,n}. Is there then a Hamiltonian path for N (there can't be a cycle). Suppose we require Hamiltonian cycles for every {a, ..., b} for a,b in Z? Can we then find a Hamiltonian path through Z?
Rich grumbles: << Could we be a bit more specific about what a Path or Cycle on an infinite graph is supposed to mean?
Just kidding, Rich -- this is a fair question. Since a closed interval and a circle are each compact, neither one can be a subgraph of an infinite graph G that contains all vertices of G. (The open cover of a putative path or cycle consisting of the two (or one) edges containing each vertex is an open cover with no finite subcover.) So the ordinary definition of a "path" or "cycle" on a graph are ruled out for any (sub)graph containing infinitely many vertices. For a path having two endpoints or a cycle, I see no acceptable redefinition without adding at least one new vertex and changing the allowable topology. I suspect this is what Dan Hoey meant when he said "There can't be a cycle". But there are two natural ways to define a "path" containing infinitely many vertices of some graph G: 1) a map f from N into its vertex set, or 2) a map f from Z into its vertex set -- in each case such that vertices f(k) and f(k+1) have an edge between them in the graph for all k in N or Z, respectively. In an abuse of consistency, I propose calling the first one "a semi-infinite path" and the second one "a bi-infinite path". When f is a bijection in either case, we'd call such a path Hamiltonian. In each of Dan's two questions above, it would be interesting to know which of these two types of Hamiltonian cycle, if any, are implied by the hypothesis. --Dan (not the one who isn't me)