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

<sup>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$. </sup>

The only SFPs I found so far are $d(x) = d(y)$, which is self-fulfilling <strike>exactly</strike> w.r.t. complete graphs, and $d(x) \neq d(y)$, which is self-fulfilling <strike>exactly</strike> w.r.t. <strike>empty</strike> 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?