We consider the query complexity of testing local graph properties in the bounded-degree graph model.
A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.
Indeed, this formulation yields a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

While it is tempting to conjecture that every local graph property has a constant-query proximity-oblivious tester(in the bounded-degree graph testing model), this conjecture was refuted by Adler, Kohler and Peng (32nd SODA and 36th CCC, 2021).
In fact, they showed that there exist local graph properties that cannot be tested (in this model) within a number of queries that does not depend on the size of the graph.
However, their proof gives no explicit lower bound on the dependence of the query complexity on the size of the graph.

In this paper, we provide such an explicit bound.
This is done by studying the query complexity of the specific local graph property presented by Adler et al.
In a natural (but not standard) model, in which the tester is not given the size of the graph but rather only a rough approximation of this size, this property has logarithmic (in the graph's size) query complexity.
In the standard model, we only obtain a quadruple-logarithmic lower bound.

minor revision: fixing some minor errors etc

We consider the query complexity of testing local graph properties in the bounded-degree graph model.
A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.
Indeed, this formulation yields a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

While it is tempting to conjecture that every local graph property has a constant-query proximity-oblivious tester(in the bounded-degree graph testing model), this conjecture was refuted by Adler, Kohler and Peng (32nd SODA and 36th CCC, 2021).
In fact, they showed that there exist local graph properties that cannot be tested (in this model) within a number of queries that does not depend on the size of the graph.
However, their proof gives no explicit lower bound on the dependence of the query complexity on the size of the graph.

In this paper, we provide such an explicit bound.
This is done by studying the query complexity of the specific local graph property presented by Adler et al.
In a natural (but not standard) model, in which the tester is not given the size of the graph but rather only a rough approximation of this size, this property has logarithmic (in the graph's size) query complexity.
In the standard model, we only obtain a quadruple-logarithmic lower bound.