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 .
After revision:  We show that in the bounded-degree graphmodel, Hamiltonicity is not testable with one-sided error probability and query complexity o(n) vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with two-sided error .