I have tried to solve a problem and I would like to check if I have done it correctly:
Let $\mathcal{V}=(V,E)$ be a graph, i.e. $E$ is a binary relation on $V$ that is symmetric and irreflexive. We consider $\mathcal{V}$ as a structure in the vocabulary $L=\{ R\}$ where $R$ is a binary predicate and $R^\mathcal{V}=E$. Find statements that express in $\mathcal{V}$ the following: (a) The graph has a clique (a complete subgraph) of $5$ or more vertice. (b) The graph is not complete, i.e. not every pair of vertices is connected by an edge.
(a) A graph has a clique of $5$ or more vertices if and only if there exist $5$ vertices, let us denote them by $x$, $y$, $z$, $u$ and $v$, such that $x\neq y$, $x\neq z$, $x\neq u$, $x\neq v$, $y\neq z$, $y\neq u$, $y\neq v$, $z\neq u$, $z\neq v$, $u\neq v$ and the pairs of vertices $(x,y)$, $(x,z)$, $(x,u)$, $(x,v)$, $(y,z)$, $(y,u)$, $(y,v)$, $(z,u)$, $(z,v)$, $(u,v)$ are connected by edges.
Hence, we obtain the formula
$$\exists x\exists y\exists z\exists u\exists v(\neg x=y\wedge \neg x=z\wedge \neg x=u\wedge \neg x=v\wedge \neg y=z\wedge \neg y=u\wedge \neg y=v\wedge \neg z=u\wedge \neg z=v\wedge \neg u=v\wedge Rxy\wedge Rxz\wedge Rxu\wedge Rxv\wedge Ryz\wedge Ryu\wedge Ryv\wedge Rzu\wedge Rzv\wedge Ruv)$$
(b) A graph is not complete if and only if there exist two different vertices not connected by an edge.
Hence, we obtain the formula
$$\exists x\exists y(\neg x=y\wedge \neg Rxy)$$
Best Answer
This looks right. Re: (a), note that "indexed connectives" can simplify things: what you've written is equivalent to $$\exists x_1,x_2,x_3,x_4,x_5[(\bigwedge_{1\le i<j\le 5}\neg x_i=x_j)\wedge(\bigwedge_{1\le i<j\le 5}R(x_i,x_j))].$$
This indexed connective notation isn't actually part of the formalism of first-order logic, but it's a commonly-used abbreviation system which $(i)$ is automatic to unpack (so it's clear that the writer could have written out a genuine FOL expression) and $(ii)$ often much more readable.