HAMILTONIAN PATHS IN INFINITE-GRAPHS

A tight connection is exhibited between infinite paths in recursive trees and Hamiltonian paths in recursive graphs. A corollary is that determining Hamiltonicity in recursive graphs is highly undecidable, viz, SIGMA-1(1)-complete. This is shown to hold even for highly recursive graphs with degree bounded by 3. Hamiltonicity is thus an example of an interesting graph problem that is outside the arithmetic hierarchy in the infinite case.