On Tue, 3 Dec 2002 asimovd@aol.com wrote:

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

Thanks for both of these counter-examples. I particularly like Dan A's since one of my colleagues was trying to get me to buy an argument that the statement is true if the degrees of the vertices were bounded. I was not convinced, but had difficulty explaining why I wasn't. Now I can just say, "behold". Edwin