Assuming that one needs $k$ quantifiers to express that a graph contains an $k$-cycle, $\lfloor n/2 \rfloor$ counting quantifiers suffice to express that a graph is an $n$-cycle:
G has exactly $n$ nodes, each node has exactly 2 neighbors, and G doesn't contain a 3-cycle, a 4-cycle, ... and an $\lfloor n/2 \rfloor$-cycle.
Question: Can be shown, that one needs at least $\lfloor n/2 \rfloor$ counting quantifiers to express that a graph is an $n$-cylce? And how?
The previous answer showed that quantifier rank $\log_2(k) \pm 1$ is sufficient and necessary for expressing "A is a $k$-cycle". This implies a lower bound of at least $\log_2(k)$ quantifiers, but not an upper bound since quantifier rank counts nesting-depth of quantifiers and not the number of quantifiers. However, it is possible to express "A is a $k$-cycle" with $O(\log k)$ quantifiers. Here is an explicit expression:
You start saying that every vertex has degree exactly two. These are $4$ quantifiers. Next we need to say that every two vertices $x$ and $y$ of the graph are connected by a path of length at most $k$. Let $P_k(x,y)$ denote this predicate. The naive way to express $P_k(x,y)$ requires $k$ quantifiers. A less naive way could use divide-and-conquer but, if we do it directly without any additional trick, the result would still be $k$ quantifiers. The final solution will be to add a trick to the divide and conquer solution.
The divide and conquer solution goes as follows: you quantify the middle vertex $z$ and then recurse on the halfs $x$-$z$ and $z$-$y$ by requiring that both $P_{k/2}(x,z)$ and $P_{k/2}(z,y)$ hold. An easy computation shows that this method produces $k$ quantifiers. To improve and achieve $O(\log k)$ quantifiers we make use of a "reusing trick" that those familiar with computational complexity will recognize from the proof that QBF is PSPACE-complete: you quantify the middle vertex $z$ and then say: for every $u$ and $v$, if $u = x$ and $v = z$, or $u = z$ and $v = y$, then $P_{k/2}(u,v)$. This recursive formula expresses the same as before but now $P_{k/2}$ is used recursively only once. This gives the $O(\log k)$ quantifiers that we want.
Finally, in order to complete the formula expressing "A is a $k$-cycle" we need to say that every vertex $x$ is connected by a path of length exactly $k$ to itself. This we can do with $O(\log k)$ quantifiers using the same trick that we used for $P_k$.
(Note: all this is much easier to argue if $k$ is an exact power of $2$ but can be made to work for any $k$).
If A and B are cycles of length m, n, then the duplicator can win the k-long Ehrenfeucht-Fraisse game iff m, n > 2^(k-1).
Basically, whatever player I moves in A, player II choose an arbitrary element in B. The rest of the strategy is the same as for linear orders.
This means that A and B are elementarily equivalent up to quantifier-rank [log_2 min(n,m)] + 1. In particular, need at least log_2 k + 1 quantifiers to express "A is a k-cycle".
(I may have gotten the quantifier-rank wrong by +- 1, but should still be basically log2 k )
