# First-order sentences characterising regularity of a graph?

Prompt:
Let L be a first-order language with a non-logical symbol E (edge relation).
We consider simple graphs (satisfies $\forall x [¬E(x,x)]$ and $\forall x \forall y [E(x,y) \Rightarrow E(y,x)]$).

The problem is to find a (finite) sentence, or (infinite) set of (finite) sentences that characterises regularity (every vertex has the same degree) of any given simple graph .

Here's my attempt:
First let $\sigma _{n}$ be the sentence (with $\Rightarrow$ as the main scope): $$\exists x \exists y_{1} \exists y_{2} \ldots \exists y_{n} \left [ \bigwedge_{i=1}^{n} E(x,y_{i}) \wedge \bigwedge_{1 \leq i \neq j \leq n}¬(y_{i} = y_{j}) \; \wedge \; \forall z [ E(x,z) \Rightarrow \bigvee_{i=1}^{n}z=y_{i} ] \right ] \Rightarrow \forall x \exists y_{1} \exists y_{2} \ldots \exists y_{n} \left [ \bigwedge_{i=1}^{n} E(x,y_{i}) \wedge \bigwedge_{1 \leq i \neq j \leq n}¬(y_{i} = y_{j}) \; \wedge \; \forall z [ E(x,z) \Rightarrow \bigvee_{i=1}^{n}z=y_{i} ] \right ]$$ i.e. $\sigma_{n}$ says If we have a vertex with exactly $n$ degrees, then all vertices have exactly $n$ degrees.
I will write the case of $0$ degrees separately: $$\exists x \forall y \left [ ¬E(x,y) \right ] \Rightarrow \forall x \forall y \left [ ¬E(x,y) \right ]$$

Then my set of sentences is: $$\left \{ \exists x \forall y \left [ ¬E(x,y) \right ] \Rightarrow \forall x \forall y \left [ ¬E(x,y) \right ] \right \} \cup \left \{ \sigma_{n} \; | \; n \in \mathbb{N}, n \geq 1 \right \}$$

Now suppose we have a regular graph, then all vertices have the same degree, call the degree $k$. Then $\sigma_{k}$ is satisfied. There's also no vertex of degree $l$ $\forall l \in \mathbb{N}, l \neq k$, so $\sigma_{l}$ and the $0$-degree case are also satisfied (false antecedent). So the whole set of sentences is satisfied.

Suppose we have a graph that's not regular. Then there's at least 2 vertices with different degree, let these degrees be $k$ and $l$, $k \neq l$. Then the antecedent of $\sigma_{k}$ and $\sigma_{l}$ are both satisfied, but not all vertices have degree $k$ nor $l$ because we know at least one of them is $k$, and another $l$. So the whole of $\sigma_{k}$ and $\sigma_{l}$ are not satisfied, so the whole set of sentences is not satisfied.

Here's my question:
What went wrong in the attempt above?
I'm aware that there's a proof that graph regularities cannot be axiomatised using a single sentence. I was also told that there's also a proof to the same effect for infinite set of sentences but I couldn't find it and that it requires more technicalities.
That aside, a professor told me that the problem have something to do with vertices with infinite degree, but I am still confused?

• You found countably infinitely many sentences $\sigma_0,\sigma_1,\sigma_2,\dots$ that together indeed characterize the locally finite regular graphs (i.e. in which every vertex has finite degree), but bigger infinite graphs are out of scope. – Berci May 3 '14 at 12:38
• What is the meaning of the adjective local in context of graph theory? – Sylin May 3 '14 at 12:39
• I meant that every vertex has finite degree, but the graph may have infinitely many vertices. (E.g. the graph on $\Bbb Z$ where each $n$ is connected only to $n+1$ is regular of degree $2$, but is an infinite graph.) – Berci May 3 '14 at 12:40
• Ah so the sentences are fine as long as we don't allow infinite degrees but infinite number of vertices or edges are fine. – Sylin May 3 '14 at 12:54

Let $V=(-\infty,0)\cup \mathbb N$ and $E(x,y)\equiv (x\ne y\land xy>0)$. Then all your $\sigma_n$ (including $\sigma_0$) are true. Yet some vertices have degree $\aleph_0$, some have degree $2^{\aleph_0}$. Also, there is no $n\in\mathbb N_0$ such that this graph is regular of degree $n$.