Can a regular directed graph be axiomatized in first order Logic?

Question

Given the first order edge relation $E$ is it possible to axiomatize directed graphs where every vertex has an equal amount of incoming and outgoind edges, including graphs with infinite edges?

Answer 1

For any fixed $n$ the statement "the vertex $x$ has in-degree $n$", and the statement "the vertex $x$ has out-degree $n$" are both first order.

Indeed if $E(x,y)$ means there is an edge going from $x$ to $y$, and if $n>0$ then

$$ \varphi_n(x)= \exists x_0, \ldots, x_{n-1}\; \left( \bigwedge_{\substack{i,j < n \\ i \neq j}} x_i \neq x_j \land \bigwedge_{i < n}E(x_i, x) \land \left(\forall y\; E(y,x) \rightarrow \bigvee_{i<n} y=x_i \right)\right)$$

means $x$ has exactly $n$ different incoming edges (it has in-degree $n$), whereas

$$ \psi_n(x)= \exists x_0, \ldots, x_{n-1}\; \left( \bigwedge_{\substack{i,j < n \\ i \neq j}} x_i \neq x_j \land \bigwedge_{i < n}E(x,x_i) \land \left(\forall y\; E(x,y) \rightarrow \bigvee_{i<n} y=x_i \right)\right)$$

means $x$ it has exactly $n$ outcoming edges (it has out-degree $n$). If you like you can also write predicates $\varphi_0(x)$ and $\psi_0(x)$ stating there are no incoming or outcoming edges respectively to $x$.

Edit

If you want a theory whose models are the graphs in which for each vertex the in-degree mathces the out-degree, you just need to add a numerable axiom schema $\mathcal{A}=\{\forall x, \varphi_n(x) \leftrightarrow \psi_n(x)\}_{n \in \mathbb{N}}$.

Instead to get a theory whose models are all the directed graphs such that:

for all nodes $x,y$ the in-degree of $x$ and $y$ are equal, and the out degree of $x$ and $y$ are equal

(which, as I understood from the comments, should be what you are looking for) it suffices add to the axiom schemata $\mathcal{B}=\{\forall x \forall y \varphi_n(x) \leftrightarrow \varphi_n(y)\}_{n \in \mathbb{N}}$ and $\mathcal{C}=\{\forall x \forall y \psi_n(x)\leftrightarrow \psi_n(y)\}_{n \in\mathbb{N}}$.

Edit 2

As for managing infinite in-degrees and out-degrees: the best you can do is an axiom schema in which you say that either all nodes have the same finite in-degree or all nodes have infinite in-degrees. And an analogue for out-degrees.

You can do it as follows: let $\varphi_{\ge n}(x)$ be the satement "x has in-degree $\ge n$", that is

$$ \varphi_{\ge n}(x)= \exists x_0, \ldots, x_{n-1}\; \left( \bigwedge_{\substack{i,j < n \\ i \neq j}} x_i \neq x_j \land \bigwedge_{i < n}E(x_i, x) \right)$$

then the axiom schema $$\mathcal{D}=\{ \big(\forall x\forall y, \, \varphi_{\ge n}(x)\rightarrow \varphi_{\ge n+1}(y)\big) \lor \big( \forall x \forall y \varphi_{m}(x) \leftrightarrow \varphi_m(y) \big)\}_{n,m \in \mathbb{N}}$$

tells you that either all nodes have the same finite in degree or all nodes have infinite in-degree: indeed if there is a node with finite degree $n$ then $\forall x\forall y, \, \varphi_{\ge n}(x)\rightarrow \varphi_{\ge n+1}(y)$ is false hence $\mathcal{D}$ is satisfied only if for every $m$ one has $\forall x \forall y \varphi_{m}(x) \leftrightarrow \varphi_m(y)$. If instead all nodes have infinite in-degree $\forall x\forall y, \, \varphi_{\ge n}(x)\rightarrow \varphi_{\ge n+1}(y)$ holds for all $n$ and $\mathcal{D}$ is satisfied.

You can add a similar axiom schema for the out-degrees.

You cannot however have a first order theory of regular directed graphs that can force nodes to have have all the same infinite cardinal as in-degrees (or out-degrees).

Indeed any dense linear order without extrema is a directed graph. For example $(\mathbb{Q}, <)$ where you take $<$ as edge relation is a regular directed graph. Now note that $(\mathbb{Q} \cup [0,1], <)$, where $[0,1]$ is a real interval, still is a dense linear orded without extrema, but all $x>0$ have $2^{\aleph_0}$ in-degree, whereas all $x\le 0$ have $\aleph_0$ in-degree.

Since the theory of dense linear orders without extrema is complete you have that $(\mathbb{Q}, <)$ and $(\mathbb{Q} \cup [0,1], <)$ are elementarily equivalent and hence every first order theory in the signature $\{<\}$ having $(\mathbb{Q}, <)$ as a model has also $(\mathbb{Q} \cup [0,1], <)$ as a model.