Date: Tue, 3 Dec 2002 12:00:32 -0500 (EST)
From: Dan Hoey <Hoey@aic.nrl.navy.mil>
To: Math-fun@mailman.xmission.com
Subject: Re: [math-fun] Square (& other) chains and necklaces.

Dan Asimov wrote:

> 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,...}.

(This is a slight modification of Dan's graph.)

4--3--5--7--9---11---
   | /| /| /|  / |  / ...
   |/ |/ |/ | /  | /
1--2--6--8--10---12--

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?

Dan (not that Dan, this Dan)
Hoey@AIC.NRL.Navy.Mil