5 Fixed typo

I've found a necessary and sufficient characterization for when a relation $\Phi$ is nontrivially self-fulfilling, in the theorem below.

(As Aaron pointed out, every $\Phi$ is realized trivially in the graph with no vertices and also in the graph with one vertex, so by nontrivially self-fullfilling, let us insist that the graph have at least two vertices. Let us speak of undirected graphs with no loops, so that we adopt Aaron's correction that a binary relation $\Phi$ on $\mathbb{N}$ is self-fulfilling in graph $\langle V,R\rangle$ just in case $x\mathrel{R} y\iff \Phi(d(x),d(y))$ and $x\neq y$.)

Theorem. A symmetric binary relation $\Phi$ on $\mathbb{N}$ is nontrivially self-fulfilling in some graph if and only if $\neg\Phi(0,0)$ or $\Phi$ is not a subrelation of $\{0\}\times\mathbb{N}\cup\mathbb{N}\times\{0\}$; that is, if and only if $\neg\Phi(0,0)$ or it has $\Phi(n,k)$ for some $n,k\neq 0$.

Proof. If $\Phi(n,n)$ holds for some $n\neq 0$, then $\Phi$ is self-fulfilling in the complete graph on $n+1$ vertices. All vertices have degree $n$, and so only $d(x)=n$ arises in this graph, and so only $\Phi(n,n)$ is relevant when checking the self-fulfilling property.

Otherwise, if $\Phi(n,k)$ holds for some $n\neq 0\neq k$, but $\Phi(n,n)$ and $\Phi(k,k)$ both fail, then $\Phi$ is self-fulfilling in the bipartite graph $B(n,k)$, having $n$ nodes on the left connected to each of $k$ nodes on the right. In this graph, if $x$ and every vertex has degree either $y$ have an edge, then k$or$\Phi(d(x),d(y))$, n$, and so one of them must have degree $0$, which contradicts that they have an edge. So there all such vertices are no connected by edgesin the graph. In this case, every vertex has fulfilling $d(x)=0$.\Phi$. If$\neg\Phi(0,0)$, then$\Phi$is self-fulling in the graph on any number of vertices, but with no edges. Again, every vertex in this graph has$d(x)=0$, and so the only relevant part of$\Phi$is$\Phi(0,0)$, which fails, and none of them are connected, as required. Otherwise,$\Phi$only relates numbers to$0$and$\Phi(0,0)$holds. No such$\Phi$can be self-fullfilling in a graph with at least two nodes$x\neq y$, since if there are no edges in the graph, then$d(x)=d(y)=0$, and so they would have to be connected because of$\Phi(0,0)$, contradiction. And if there is an edge in the graph between some$x$and$y$, then$d(x)$and$d(y)$have some value for which$\Phi(d(x),d(y))$, but by assumption one of those values must be$0$, contradicting the fact that there is an edge. QED Note that the graphs arising in the proof have vertices only of very few degrees, which makes the self-fulfilling property easier. Here is the example I gave earlier, which does have vertices of every non-zero degree. The relation$|d(y)-d(x)|=1$seems to be self-fulfilling in the following graph, where each node is labeled with its degree. One can construct the graph in levels, where at each level, the degree increases by$1$, and the number of nodes on the next level is determined by the self-fulfilling requirement. Each node on each level is connected to all nodes on any prior or next level.  ....... etc. 11 11 11 11 11 (each 11 is connected to five 10s and six 12s) 10 10 10 10 10 (each 10 is connected to five 9s and five 11s) 9 9 9 9 9 (each 9 is connected to four 8s and five 10s) 8 8 8 8 (each 8 is connected to three 7s and five 9s) 7 7 7 (each 7 is connected to three 6s and four 8s) 6 6 6 (each 6 is connected to three 5s and three 7s) 5 5 5 (each 5 is connected to two 4s and three 6s) |//\\| 4 4 \ / 3 | 2 | 1  The sizes of the levels grows in the pattern: three of the same size, then one level with one more, then three of the same size one step larger, etc. It seems that this idea can be generalized to make many more examples where the degrees increase in levels. 4 Added necessary and sufficient characterization Well I've found a necessary and sufficient characterization forwhen a relation$\Phi$is nontrivially self-fulfilling, here's another inthe theorem below. (As Aaron pointed out, every$\Phi$is realized triviallyin the graph with no vertices and also in the graph withone vertex, so by nontrivially self-fullfilling, let usinsist that the graph have at least two vertices. Let usspeak of undirected graphs with no loops, so that we adoptAaron's correction that a binary relation$\Phi$on$\mathbb{N}$is self-fulfilling in graph$\langleV,R\rangle$just in case$x\mathrel{R} y\iff\Phi(d(x),d(y))$and$x\neq y$.) Theorem. A symmetric binaryrelation$\Phi$on$\mathbb{N}$is nontriviallyself-fulfilling in some graph if and only if$\neg\Phi(0,0)$or$\Phi$is not a subrelation of$\{0\}\times\mathbb{N}\cup\mathbb{N}\times\{0\}$; thatis, if and only if$\neg\Phi(0,0)$or it has$\Phi(n,k)$for some$n,k\neq 0$. Proof. If$\Phi(n,n)$holds for some$n\neq 0$, then$\Phi$is self-fulfilling in the complete graph on$n+1$vertices.All vertices have degree$n$, and so only$d(x)=n$arisesin this graph, and so only$\Phi(n,n)$is relevant whenchecking the self-fulfilling property. Otherwise, if$\Phi(n,k)$holds for some$n\neq 0\neq k$,but$\Phi(n,n)$and$\Phi(k,k)$both fail, then$\Phi$isself-fulfilling in the bipartite graph$B(n,k)$, having$n$nodes on the left connected to each of$k$nodes on theright. In this graph, if$x$and$y$have an edge, then$\Phi(d(x),d(y))$, and so one of them must have degree$0$,which contradicts that they have an edge. So there are noedges in the graph. In this case, every vertex has$d(x)=0$. If$\neg\Phi(0,0)$, then$\Phi$is self-fulling in thegraph on any number of vertices, but with no edges. Again,every vertex in this graph has$d(x)=0$, and so the onlyrelevant part of$\Phi$is$\Phi(0,0)$, which fails, andnone of them are connected, as required. Otherwise,$\Phi$only relates numbers to$0$and$\Phi(0,0)$holds. No such$\Phi$can be self-fullfillingin a graph with at least two nodes$x\neq y$, since ifthere are no edges in the graph, then$d(x)=d(y)=0$, and sothey would have to be connected because of$\Phi(0,0)$,contradiction. And if there is an edge in the graph betweensome$x$and$y$, then$d(x)$and$d(y)$have some valuefor which$\Phi(d(x),d(y))$, but by assumption one of thosevalues must be$0\$, contradicting the fact that there is anedge. QED

Note that the graphs arising in the proof have vertices only of very few degrees, which makes the self-fulfilling property easier.

Here is the example I gave earlier, which does have vertices of every non-zero degree.

3 Added characterization; added 19 characters in body; deleted 2701 characters in body
2 deleted 2 characters in body; added 153 characters in body
1