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?
> 
> 
> 



Expressing a graph property with counting quantifiers
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$).


