Find a first-order logic sentence distinguishing two graphs Graph $G$ is the backbone of a cube ($8$ vertices, $12$ edges). In contrast, graph $H $ is a copy of a graph $ G $,  without exactly one edge ($8$ vertices, $11$ edges).
Write a sentence distinguishing the two graphs with minimal nesting quantifiers.
For me, it is very simple:
$ \forall_v deg (v) = 3$.
This sentence for $ G $ is true, however for $ H $ is not true. Unfortunately, it is not correct answer. I ask you for explaining me where I am wrong and how to solve it. On the whole, I have a problem with this type of task.
 A: I think you found the right property, but you didn't express it in the right way in a logical setting. When dealing with logic on graphs, a graph property is expressed by a logical formula whose variables represent graph vertices. Two predicates are allowed: equality ($v_1 = v_2$) and adjacency $E(v_1,v_2)$ interpreted as "there is an edge between $v_1$ and $v_2$. That being said, your property that all vertices have degree at least $3$ can be stated as follows:
$$
  \forall v\ \exists v_1\ \exists v_2\ \exists v_3\ \text{Diff}(v, v_1, v_2, v_3) \wedge E(v,v_1) \wedge E(v,v_2) \wedge E(v,v_3)
$$ 
where $\text{Diff}(v, v_1, v_2, v_3)$ is a sentence stating that $v, v_1, v_2, v_3$ are all distinct (I let you guess how you can express that in first order).
Wrong. However, it is possible to do better in terms of quantifier alternations: just express the fact that there exist 8 distinct vertices. You will of course need 8 existential quantifiers, but only one quantifier alternation.
EDIT. One could instead completely describe the graph $G$ by saying there exist 8 vertices, all distinct and describe all the edges of the graph. Not very concise but existential quantifiers would suffice.
A: Your sentence does indeed distinguish the two graphs. However, it is not of minimal quantifier complexity. Saying "all vertices have degree $3$" is a $\forall \exists^3\forall$-sentence (I don't know if the problem wants you to count every quantifier, or just alternations): "for every vertex, there exist three distinct vertices such that all vertices connected to the original are equal to one of the three".
EDIT: You asked for an explanation of (nesting) quantifier complexity. There are two different notions here; they each apply to sentences in prenex normal form (that is, a string of quantifiers followed by a quantifier-free formula), and basically count how many quantifiers there are. One notion of complexity counts quantifiers directly: so e.g. "$\forall x\exists y\exists z\forall a\forall b P(x, y, z, a, b)$" would have complexity $\forall\exists^2\forall^2$, or if we're going to give it a number, "$5$". The other notion of complexity counts alternations of quantifiers - similar quantifiers are "smooshed" together. So the previous sentence would be of complexity $\forall\exists\forall$, or "$3$". (Actually, in this context we like to keep track of the leading quantifier - so we'd say "$\Pi_3$" or "$\forall_3$".)
This second method may seem more ad hoc, but it's actually extremely useful especially in computability theory and set theory; see here and here. I don't know which version your class wants you to use; presumably somewhere they specifically define what kind of quantifier counting they're doing.
The point is: you want to come up with a sentence distinguishing $G$ and $H$ which uses as few quantifiers as possible.
So how are we going to improve that? Well, intuitively, deleting an edge makes a graph "less connected." So a good place to look is:

What is the smallest size of a set of vertices such that every vertex outside that set is connected to one in the set?

Good news: saying that this number is $\le n$ is an $\exists^n\forall$-statement!
Bad news: this is a non-starter: both $G$ and $H$ have $n=2$.
Good news: we can tweak this example to get one that works. HINT: abgr gung gurer ner sbhe iregvprf bs $T$ fhpu gung nal bgure iregrk vf pbaarpgrq gb guerr bs gurz . . .
EDIT: Actually J.-E. Pin's answer is better in terms of quantifier complexity. But I'll leave this up in case it's helpful.
