Let's consider two graphs: $$G_1 = <V_1, E_1>, G_2 = <V_2, E_2>$$ $$V_1 = \{1,2,..,15\}, E_1 = \{(n, 2n+1) | n, 2n+1 \in V_1\}$$ $$V_2 = \{1,2,..,11\}, E_2 = \{(n, 2n+1) | n, 2n+1 \in V_2\}$$
Find a sentence such that it distinguishes $G_1$ and $G_2$ and its QD is minimal. ( QD = Quantifier Depth) My solution: $$\exists x \exists y \exists z \exists q e(x,y) \wedge e(y,z) \wedge e(z,q)$$
Is it optimal or not?
For this question, the universe of discourse it is not fully specified, which makes it hard to give a definite answer.
Three possible universes of discourse spring to mind.
The first one, which corresponds to the kind of sentence you wrote for your solution, assumes that the graph vertex are the only thing that exists, the only predicate is the edge predicate and no constants are allowed. For that one, your solution is indeed correct.
There are 8 possible combinations of quantifiers that form sentences of QD 3. We will examine each one in turn and see why they are not sufficient to distinguish between graphs:
1) $\exists\exists\exists$ - Every subgraph of size 3 of the 15 graph is isomorphic to a subgraph of the 11 graph, so we cannot rely on identifying a dissimilar subgraph.
2) $\exists\exists\forall$ - $\exists\forall\exists$ - $\forall\exists\exists$ - there is no pair of vertices which hold a special position with respect to the rest of the graph in one graph which does not hold in the other.
3) $\exists\forall\forall$ - $\forall\forall\exists$ - $\forall\exists\forall$ - There is no single vertex with a privileged position with respect to the rest of the graph.
4) $\forall\forall\forall$ - There is no special relation between every three vertex of one graph which does not not hold in the other.
On a second universe, we are allowed to use constants. Then a possible solution becomes $\forall x \neg e(x,6)$. There is no possible solution with QD zero since the constants which are valid in both universes are related to one another in the same way in both graphs.
In a final universe, the underlying elements are natural numbers with the usual arithmetic, plus special predicates to identify the vertices and edges. In this kind of universe, it is possible to "compress" the four existential quantifiers of your solution into a single one, by forming functions which convert natural numbers into 4-uples of natural numbers through an enumeration.
This is the reason why in the arithmetical hierarchy we only count alternate quantifiers for depth; we can always compress adjacent existential quantifiers and adjacent universal quantifiers.