Hamiltonian paths in infinite graphs
David Harel · 1991
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, Z~complete.This is shown to hold even for highly recursive graphs with outdegree bounded by 3. Hamiltonicit y is thus an example of an interesting graph problem, which is outside the arithmetic hierarchy in the infinite case.The proofi in the paper are nontrivial, yet are elementary in nature.