What is a FO- Formula with quantifier rank <4 and no use of universal quantification that is satisfied by one graph and not by the other? 
Hello,
I've been trying to find a FO-formula with quantifier rank <4 and no use of universal quantification that is satisfied by one graph and not by the other, but with no such luck, I'd be grateful for any help.
it was indeed stated by my professors that it is not possible in ∃FO[σ].
It is though possible in FO[σ], as stated by them it is a formula that is in negation normal form and only the following operators can be used {∃, ∧, ∨, ¬} .
 A: EDIT: This is a great exercise in how prenex normal form is the best thing ever and not putting your quantifiers all together in a block at the start of your formula should be considered a class $1$ misdemeanor.
First, let's recall the definition of quantifier rank for (ugh) negation-normal-form formulas not involving $\forall$:

*

*Atomic formulas have rank $0$.


*Boolean combinations don't change quantifier rank.


*If $\varphi$ has rank $k$ then $\exists x\varphi$ has rank $k+1$.
In particular, the rank of a formula of the form $\exists x_1,...,x_k\theta(x_1,...,x_k)$ (that is, an $\exists^k$ formula) is $k$.
Next, we have (see below the fold) a fundamental difficulty here:

*

*No $\exists^3$ sentence can distinguish the two graphs in question. (See below.)

Finally, we have something which at first may seem to contradict the previous point:

*

*Any negation normal form formula not involving $\forall$ can be put into prenex normal form with only $\exists$s.

The point, however, is that this prenexing process can increase the quantifier rank. This is because $\exists$ and $\wedge$ don't distribute: in general, for example, a formula of the form $\exists (\exists yP(x,y)\wedge\exists zQ(x,z))$ has to be transformed into one of the form $\exists x,y,z(P(x,y)\wedge Q(x,z))$ since the witnessing $y$ and $z$ may not be the same.
So basically, you're looking for a sentence which "cheats:" it hides a secretly-high-rank behavior behind a mixture of $\exists$ and $\wedge$. Can you find one?
HINT: think about sentences of the form $$\exists x,y(A(x,y)\wedge \exists z_1(B_1(x,y,z_1))\wedge \exists z_2(B_2(x,y,z_2)))$$ for judicious choice of quantifier-free formulas $A, B_2, B_2$. Intuitively, you're looking two three-vertex graphs which occur "overlapping" (= sharing a pair of vertices: $x,y,z_1$ vs. $x,y,z_2$) in one of your two graphs but not in the other.

 In $\mathcal{T}$ the pair $a,b$ is simultaneously part of a triangle (via $c$) and part of a three-point-line (via $e$). So it witnesses $$\exists x,y(R(x,y)\wedge \exists z_1(R(x,z_1)\wedge R(y,z_1))\wedge \exists z_2(R(x,z_2)\wedge\neg R(y,z_2)).$$ But this doesn't happen in $\mathcal{S}$.


Prenex won't do the job
OK, now for completeness let's show that no $\exists^3$ sentence will do the job.
Suppose I have a sentence of the form $$\varphi:\quad\exists x_1,...,x_k\theta(x_1,...,x_k)$$ with $\theta$ quantifier-free. Whether or not a structure satisfies $\varphi$ is determined entirely by the set of atomic types of $k$-tuples occurring in that structure. Consequently we have a simple characterization of $\exists^k$-equivalence (= agreement on all sentences of the above form):

Two structures are $\exists^k$-equivalent iff they have the same sets of atomic types of $k$-tuples.

In a language with function symbols this can be difficult to check, since the atomic $k$-type of a tuple may wind up referring to infinitely many elements (via composition of functions). However, in a relational language the atomic type of a $k$-tuple can be determined just by looking at the $k$-tuple on its own. In particular, we have:

Two graphs are $\exists^k$-equivalent iff they have the same $k$-vertex induced subgraphs.

So in this particular case you want to check the following:

What are the three-vertex subgraphs occurring in each of the two graphs under consideration?

HINT: rather than checking each $3$-tuple in each structure, first list the three-vertex graphs up to isomorphism - there aren't many of these - and then check whether each one appears in each of the two graphs under consideration.
You'll quickly find that the two graphs in consideration have the same $3$-vertex induced subgraphs, and so we really do need the non-prenex-y shenanigans above.
