Boolean expressions for distinct graphs The question is to write two boolean expressions per set of graphs that differentiate between them. The domain for the expression should be all vertices in the given graph. Also, $E(x,y) =$ "there is an undirected edge between $x$ and $y$".
Set 1
 
The only difference I found between 1.1 and 1.2 was that 1.2 has an additional vertex that has an edge with the last vertex.
For 1.1: $\exists x,y,z (E(x,y) \land E(y,z) \land x \ne y \ne z)$
For 1.2, $\exists x,y,z,n (E(x,y) \land E(y,z) \land E(z,n) \land x \ne y \ne z \ne n)$
Set 2

The difference I found here was that in 2.1, if the first vertex is connected to a second vertex and the second vertex is connected to a third vertex, then the first vertex is not connected to the third vertex. However, in 2.2, all vertices are connected to each other.
For 2.1: $\forall x,y,z (x \ne y \ne z \rightarrow E(x,y) \land E(y,z) \land \lnot E(x,z))$
For 2.2: $\forall x,y (x \ne y \rightarrow E(x,y))$
Am I interpreting these graphs correctly through my boolean expressions. If I am, then is there a more concise or logical way to represent these graphs?

A few comments:


*

*$x \neq y \neq z$ is not really a good formula, but even if we would accept it, it would mean $x \neq y \land y \neq z$, in particular it may happen that $x = z$. What you want to say, is that $x,y,z$ are pairwise distinct, or formally $x \neq y \land x \neq z \land y \neq z$ (for 4 vertices you would have 6 pairs).

*Formula 1.1 doesn't distinguish between the two first graphs, because the second graph does have three vertices connected with edges. The difference is that there are only three vertices. Such condition are usually written as $\forall v\ (v = x \lor v = y \lor v = z)$ where $x,y,z$ are bound by some other quantifier.

*Formula 1.2 doesn't distingush between the two first graphs, because of the first bullet, for example $G = \{1,2\}$ and $E = \{(1,2),(2,1)\}$ would be a good model for it.

*The simplest formula that distinguishes between the two first graph checks if there exist 4 pairwise distinct vertices.

*Formula 2.1 doesn't distinguish the second pair of graphs because of the first bullet, that is we have $\neg E(x,x)$.

*Formula 2.2 works, good job ;-)


I hope this helps $\ddot\smile$
