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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Berci May 3 '14 at 12:38
  • $\begingroup$ What is the meaning of the adjective local in context of graph theory? $\endgroup$ – Sylin May 3 '14 at 12:39
  • 1
    $\begingroup$ 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.) $\endgroup$ – Berci May 3 '14 at 12:40
  • $\begingroup$ Ah so the sentences are fine as long as we don't allow infinite degrees but infinite number of vertices or edges are fine. $\endgroup$ – 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$.

  • $\begingroup$ edit Ahhh I see! $\endgroup$ – Sylin May 3 '14 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.