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, Σ ₁ ¹ -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. Parts of this research were carried out during a visit to IBM T.J. Watson Research Center, Hawthorne, NY, in the Summer of 1990. The author holds the William Sussman Professorial Chair in Mathematics.