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