Considering the bounded-degree graph model, we show that if the degree bound is two,
then every graph property can be tested within query complexity that only depends on the proximity parameter.
Specifically, the query complexity is ${\rm poly}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.
The key observation is that a ... more >>>