  We study property testing of properties that are definable in first-order
logic (FO) in the bounded-degree graph and relational structure models. We show
that any FO property that is defined by a formula with quantifier prefix
$\exists^*\forall^*$ is testable (i.e., testable with constant query
complexity), while there exists an FO property that is expressible by a formula
with quantifier prefix $\forall^*\exists^*$ that is not testable. In the dense
graph model, a similar picture is long known (Alon, Fischer, Krivelevich,
Szegedy, Combinatorica 2000), despite the very different nature of the two
models. In particular, we obtain our lower bound by a first-order formula that
defines a class of bounded-degree expanders, based on zig-zag products of
graphs. We expect this to be of independent interest. We then prove testability
of some first-order properties that speak about isomorphism types of
neighbourhoods, including testability of $1$-neighbourhood-freeness, and
$r$-neighbourhood-freeness under a mild assumption on the degrees.
