Reminds me of when I first learned of non-standard models of mathematical logic. The most powerful axiom in the Peano axioms of the integers is the induction axiom that says you can start from zero and get to any integer in a finite number of steps. Without this axiom, all sorts of wierd models work for arithmetic, including those with disconnected (finite and infinite) loops of 'integers'. At 10:01 AM 12/3/02 -0800, Marc LeBrun wrote:

...

=Richard Schroeppel Could we be a bit more specific about what a Path or Cycle on an infinite graph is supposed to mean?

Exactly the question! Now I see why I've been very confused by this part of the discussion.

If we mean by Cycle simply something like "there exists a connected subgraph with all nodes valence 2", and by Path "ditto, but allowing at most two nodes of valence 1", then I see no contradiction with the examples (and the desired proof becomes trivial).

Only if we insist that everything be FINITELY connected are these infinite hairpins a problem. But then it kind of begs the question whether the infinite graph itself is "connected" in the first place.