Here's a more general question: 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? (The converse is false as the graph 1-3-2-5-4-7-6-... shows.)

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. mike