We study property testing in the model of bounded degree graphs. It is well known that in this model many graph properties cannot be tested with a constant number of queries and it seems reasonable to conjecture that only few are testable with o(sqrt{n}) queries. Therefore in this paper we ... more >>>