  Let D(G) be the smallest quantifier depth of a first order formula which is
true for a graph G but false for any other non-isomorphic graph. This can be
viewed as a measure for the first order descriptive complexity of G.
  We will show that almost surely D(G)=\Theta(\ln n/\ln\ln n), where G is a
random tree of order n or the giant component of a random graph G(n,c/n) with
constant c>1. These results rely on computing the maximum of D(T) for a tree T
of order n and maximum degree l, so we study this problem as well.
