It will follow from our results that the enumeration problem of FO over the
class of structures with “bounded expansion” is in \(\textsc {\small CD}\!\circ \!\textsc {\small Lin}\) . The notion of
bounded expansion was defined in [1]} for graphs and then
it was generalized to structures via their Gaifman or Adjacency graphs.
We start with defining it for graphs.
