Descriptive complexity: 3-colorability example So in Neil Immerman's book http://books.google.co.kr/books?id=kWSZ0OWnupkC&amp;pg=PA113&amp;lpg=PA113#v=onepage&amp;q&amp;f=false, 3-colorability problem in descriptive complexity fashion is expressed as following: $\exists R \exists Y \exists B \forall x \left[(R(x) \vee Y(x) \vee B(x)) \wedge (\forall y) (E(x,y) \rightarrow \neg(R(x) \wedge R(y)) \wedge \neg(Y(x) \wedge Y(y)) \wedge \neg (B(x) \wedge B(y))) \right]$.

My previous question seems to have been misunderstood - I was not asking about what first-order or second-order logic is, but rather on the use of quantifier. Here $\forall x$ seems to imply that universe is already predefined to refer to vertices only. Is this correct understanding? If so, why is it the case? Is it pre-defined rule of descriptive complexity usage of logic?

Also for any similar graph problems, is universe of sets restricted to vertices only, or are we allowed to add sensible sets to universe?
The convention in descriptive complexity is that for graph properties, the universe always consists of the set of vertices, and there is an additional two-place edge relation.