Before revision:  We show that in the bounded-degree graphmodel, Hamiltonicity is not testable with one-sided error probability and query complexity o(n) . This contrasts the known fact that on planar (or minor-free) graph classes, Hamiltonicity is testable with constant query complexity in the bounded-degree graph model with two-sided error . Our proof is an intricate construction that shows how to turn a d-regular graph into a graph that is far from being Hamiltonian, and we use d-regular expander graphs to maintain local Hamiltonicity .
After revision:  We show that in the bounded-degree graphmodel, Hamiltonicity is not testable with one-sided error probability and query complexity o(n) . This contrasts the known fact that on planar (or minor-free) graph classes, Hamiltonicity is testable with constant query complexity in the bounded-degree graph model with two-sided error ) requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010). This is proved via a randomised construction of hard instances. In contrast, our construction is deterministic. So far only very few deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties hat are testable in the bounded-degree model .