The first order definability of graphs: Upper bounds for quantifier depth

Let D(G) denote the minimum quantifier depth of a first order sentence that defines a graph G up to isomorphism in terms of the adjacency and equality relations. Call two vertices of G similar if they have the same adjacency to any other vertex and denote the maximum number of pairwise similar vertices in G by σ(G). We prove that σ(G)+1?D(G)?max{σ(G)+2,(n+5)/2}, where n denotes the number of vertices of G. In particular, D(G)?(n+5)/2 for every G with no transposition in the automorphism group. If G is connected and has maximum degree d, we prove that for a constant . A linear lower bound for graphs of maximum degree 3 with no transposition in the automorphism group follows from an earlier result by Cai, Fürer, and Immerman An optimal lower bound on the number of variables for graph identification, Combinatorica 12(4) (1992) 389-410]. Our upper bounds for D(G) hold true even if we allow only definitions with at most one alternation in any sequence of nested quantifiers.In passing we establish an upper bound for a related number D(G,G^′), the minimum quantifier depth of a first order sentence which is true on exactly one of graphs G and G^′. If G and G^′ are non-isomorphic and both have n vertices, then D(G,G^′)?(n+3)/2. This bound is tight up to an additive constant of 1. If we additionally require that a sentence distinguishing G and G^′ is existential, we prove only a slightly weaker bound D(G,G^′)?(n+5)/2.