# 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?

## 1 Answer

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$

• Thanks! One question regarding 1.1 - if I revised it as $\exists x,y,z \forall v ((v = x) \lor (v = y) \lor (v = z)) \land E(x,y) \land E(y,z) \land ( (x \ne y) \land (x \ne z) \land (y \ne y))$, then would that differentiate 1.1 from 1.2? – Shrey Sep 21 '16 at 18:17
• Also, generally speaking and following from the 1.1 and 1.2 examples - you said that the best formula checks if there are distinct pairwise vertices. It's easy to write out the pairs, like $E(x,y) \land E(y,z)$, if you have three vertices, but what if you have $n$ vertices? How do you generalize it? – Shrey Sep 21 '16 at 18:28
• @Shrey It does. Because of the difference in number of vertices, even $\exists x,y,z\ \forall v\ (v = x \lor v = y \lor v = z)$ would be enough. On the other hand, if you want to represent the graph exactly, then you need to include edges. Your formula does that, but it lacks things like $\neg E(x,z)$, thus it wouldn't differentiate between the first example and a triangle (i.e. graph $K_3$). – dtldarek Sep 21 '16 at 19:27
• For any concrete graph you can write down all the pairs, and although it might take really long, theoretically you can do it. For $n$ vertices you have $\frac{n(n-1)}{2}$ pairs, so for $n=5$ formula looks like $$\exists a,b,c,d,e\ (a \neq b \land a \neq c\land a\neq d \land a \neq e \land b \neq c \land b \neq d \land b\neq e \land c \neq d \land c \neq e \land d \neq e).$$ In general you can usually write it like this: $$\exists v_1,\ldots,v_n \left(\bigwedge_{1 \leq i < j \leq n}v_i \neq v_j\right).$$ – dtldarek Sep 21 '16 at 19:32
• Also, note, the last formula is a valid first-order logic formula only if $n$ is some concrete number known beforehand, and not a variable (so that, if someone would be persistent enough, he could theoretically write it down without using ellipsis $\cdots$ or big-wedge $\bigwedge_{i}$ notation). – dtldarek Sep 21 '16 at 19:39