Graph Theory and First-Order Logic

I'm studying some lectures on Graph Theory and I'm having some trouble translating the following statement to First-Order Logic.

Every vertex has degree n-2, where n is the number of vertices on the graph.

Given P(x,y)="All vertex pairs that there's a path connecting them" and E(x,y)="There's an edge connecting the pair" (we cannot use the same variable i.e (x,x))

I'd appreciate any help

• Assuming that graphs are defined to not have loops, the sentence you want to translate is equivalent to "for every vertex $x$ there is exactly one vertex $y$ that is neither equal to $x$ nor adjacent to $x$." Commented Apr 13, 2021 at 15:28
• @AndreasBlass that is a correct inference, but do we want to skip ahead to that or just frame (translate) the statement as given? Commented Apr 13, 2021 at 15:50
• @Joffan How can we do that? I'd be interested in seeing an answer that does this. Commented Apr 13, 2021 at 16:18
• @AndreasBlass pretty much solved it right? The sentence is $\forall _x \exists_y (x\neq y \wedge \neg E(x,y)\wedge \forall _z (z=y \vee z=x \vee E(z,x)))$ Commented Apr 13, 2021 at 17:15

AndreasBlass pretty much solved it in the comments for graphs with no self loops and no multiple edges. The sentence can be taken for instance as

$$\forall _x \exists_y (x\neq y \wedge \neg E(x,y)\wedge \forall _z (z=y \vee z=x \vee E(z,x))).$$

It says that for all $$x$$ there is a distinct $$y$$ not adjacent to $$x$$, and moreover all vertices $$z$$ not equal to $$y$$ or $$x$$ are adjacent to $$x$$.

For graph with no self loops:

$$\forall x\in V,\enspace\nexists \text{ distinct } i,j\in V\setminus\{x\},s.t.\enspace\neg P(x,i)\wedge \neg P(x,j)$$ and $$\exists i\in V\setminus\{x\} s.t.\enspace\neg P(x,i)$$

For graph where we allow loops:

$$\forall x\in V,\quad \nexists \text{ distinct } i,j,k\in V,s.t.\quad \neg P(x,i)\wedge \neg P(x,j)\wedge \neg P(x,k)$$ and $$\exists \text{ distinct } i,j\in V s.t.\quad \neg P(x,i)\wedge \neg P(x,j)$$

• If $x$ is adjacent to neither $i$ nor $j$, then the degree of $x$ is at most $n-3$. Commented Apr 13, 2021 at 15:57
• one of $i,j$ can be x itself? specifically, I have not assumed no self loops. Commented Apr 13, 2021 at 16:13
• But suppose it isn't? Commented Apr 13, 2021 at 16:15
• @saulpatz. I didn't get you. All i'm saying is that there exist 2 other vertices (but not 3 vertices) amongst the |V| vertices that every vertex $x\in V$ is not connected to. This gives us a degree of $n-2$ for each vertex. Commented Apr 13, 2021 at 16:50
• The maximum degree of a vertex is $n-1$, not $n$. Commented Apr 13, 2021 at 16:54