# Countable graph that is “as non-traceable as it gets”

If $\omega$ denotes the set of the natural numbers (= the first infinite ordinal), and if $E\subseteq\binom{\omega}{2}$ is any subset, we call a map $f\colon\omega\to\omega$ a walk in the graph $(\omega,E)$ if and only if $\{f(k),f(k+1)\}\in E$ for all $k\in\omega$.

We call $f$ a walk a Hamiltonian walk1 if and only if it is surjective.

Question.

Is there $E \subseteq \binom{\omega}{2}$ such that

1. there is at least one Hamiltonian walk in $(\omega,E)$,
2. every Hamiltonian walk in $(\omega,E)$ visits every vertex infinitely-often?

Remarks.

• A walk need not be injective, nor need it be surjective.

• Condition 1. implies that $(\omega,E)$ is a connected graph.

• In graph theory, an injective walk is called a path. (This is accidentally different from the usual convention in topology, where the term 'path' signals that self-intersections are permitted.)

• In graph theory, a graph admitting an injective and surjective walk into it is called traceable. (For finite graphs, the term Hamiltonian most often means that there exists a Hamilton path whose end-vertices are adjacent, i.e., a Hamilton circuit. For infinite graphs, this does not make sense (simply because then a Hamilton path does not have two "end-vertices"), which necessitates either (0) keeping to the study of Hamilton-paths only, or (1) using definitions involving some kind of 'convergence'.) This explains the focus of this question on Hamilton-paths, and the title of the OP.

1This terminology harmonizes rather well with e.g. the book Futaba Fujie, Ping Zhang: Covering Walks in Graphs. SpringerBriefs in Mathematics, 2014.

• Re " the proper term for a not necessarily injective "path" ": the usual convention is that this is just 'path'. For the record: 'path'='continuous map $[0,1]\to$(the space)', while 'arc'='map $[0,1]\to$(the space) which is a homeomorphism onto its image'. The latter condition is equivalent to 'injective' if (the space) is a Hausdorff space.) Note that this convention jarrs with the usual graph-theoretic convention which has 'path'='walk without any repetitions whatsoever'. This is just historical hazard. – Peter Heinig Sep 26 '17 at 12:46
• Wouldn't a two-sided infinite path do? – Wojowu Sep 26 '17 at 12:56
• @Dominic van der Zypen: extensive edits were made to your OP. I think that all these edits are right. In particular, the connectedness-condition was superfluous and misleading, unless I am missing something obvious. The term 'Hamiltonian walk' is an attested technical term. And Wojowu answered your question, and should perhaps make it an official answer. – Peter Heinig Sep 26 '17 at 14:01
• What about an infinite tree with all vertex degrees equal to 3? This works even for a path infinite in both directions. – Ilya Bogdanov Sep 26 '17 at 15:38
• What about $G=K_2$? – Jan Kyncl Sep 27 '17 at 0:04