Edwin Clark asked: << Let G be a graph whose vertices are N, the natural numbers. Suppose for every n the subgraph G_n of G induced on {1,2,...,n} has a Hamiltonian path starting with 1. Does G necessarily have a Hamiltonian path?
MIke Reid wrote: << no. a simple counterexample is the graph 4 --- 3 --- 6 --- 7 --- 8 --- 9 -- ... | \_ | _/ | \ | / ... 1 --- 2 --- 5 where 5 is connected to n for all n > 5 (as well as to 2 and 3 ). Since 1 and 4 each have degree 1 , they would both have to be endpoints of any infinite hamiltonian path, a contradiction.
Nice example! Now suppose every vertex is required to have finite valence. Then I think this slight modification of Mike's example will still serve as a graph where every {1,...,n} has a Hamiltonian path, but not {1,2,3,...}. 4 --- 3 --- 6 --- 7 --- 9 --- 11 ... |\_ | _/ | _/ | _/ | | \ | / | / | / | 1 --- 2 --- 5 --- 8 --- 10 ---12 ... --Dan