Graph Theory and First-Order Logic

Question

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

Answer 1

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$.

Answer 2

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)$