The relations $R$ in abstract graphs (with genuinely propertyless vertices) cannot be defined because there is nothing the relations can base on: they have to be presupposed.

But consider derived relations $\Phi(x,y)$ between vertices of a graph which can be defined in terms of the base relation $R$. I don't want to fix a language, but as an example I have in mind relations of the form $\phi(d(x),d(y))$, with $d(x)$ the degree of $x$ (with respect to $R$) and $\phi(n,m)$ a relation between natural numbers.

Definition: $\Phi$ is a self-fulfilling property (SFP) w.r.t. $G$ iff $\Phi(x,y) \equiv Rxy$ for all $x,y \in G$.

^{The other way round: $G$ is a self-defining structure w.r.t. $\Phi$ iff $\Phi(x,y) \equiv Rxy$ for all $x,y \in G$.}

The only SFPs I found so far are $d(x) = d(y)$, which is self-fulfilling exactly w.r.t. complete graphs, and $d(x) \neq d(y)$, which is self-fulfilling exactly (?) w.r.t. empty edgeless graphs. Can anyone come up with more intriguing examples?

What else can be said about SFPs?

• Can we decide whether there is a graph $G$ for which a given $\Phi$ is an SFP? Can we construct such a graph?

• Can we decide whether there is an SFP $\Phi$ for a given graph $G$?

• How can graphs with an SFP be characterized?