Before revision:  We exhibit classes of graphs of bounded degree that are locally Hamiltonian, i. e.  every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph , but that are far from being Hamiltonian. We then use these classes to obtain a lower bound in property testing. 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 .
After revision:  We exhibit classes of graphs of bounded degree that are locally Hamiltonian, i. e. every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph . More precisely, we obtain graphs which differ in \Theta(n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of 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 .