Skip to main content
3 of 3
added 321 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I suppose we are implicitely appending $x \neq y \land \dots$ to all relations lest we get loops. Also, every binary relation is (vacuously) self fulfilling for the empty and 1 point graphs. Hence we should specify at least two vertices.

Graphs with no edges are characterized by any empty relation such as $d(x) \neq d(x)$ or $d(x)d(y) \neq d(x)d(y)$ or merely $\emptyset$. For complete graphs $d(x)=d(x)$ or $d(x)d(y)=d(x)d(y)$ could work.

The relation $\Phi$ has to be symmetric if we want an undirected graph. So, for undirected graphs with at least two points, $d(x)=d(y)^2$ would specify the one edge path.

If the relation was "exactly one of $d(x),d(y)$ is less than 2" we would get stars . If the relation was $\lbrace d(x),d(y) \rbrace=\lbrace 3,7 \rbrace \textbf{ OR } d(x)d(y)=0$ we would get the 10 vertex 21 edge complete multipartite graph $K_{3,7}$. The last condition is intended to forbid isolated vertices.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104