We study first-order definitions of graph properties over the vocabulary consisting of
the adjacency and order relations. We compare logical complexities of subgraph
isomorphism in terms of the minimum quantifier depth in two settings: with and
without the order relation. We prove that, for pattern-trees, it is at least (roughly)
two times smaller in the former case. We find the minimum quantifier depths of
-sentences
defining subgraph isomorphism for all pattern graphs with at most
vertices.
