Suppose $\sigma$ is a vocabulary of First Order logic consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence (FO formula with no free variables). Is it decidable whether there is a finite directed graph $G$, with all in- and out-degrees $0$ or $1$, such that $G\models \phi$ ?
Decidability over finite graphs of small degree
graphs;logic;undecidability;first order logic;finite model theory