$n \equiv 0 \pmod 4$ or $n \equiv 1 \pmod 4$

$n \equiv 2 \pmod 4$ or $n \equiv 3 \pmod 4$

The number of edges must be $\frac{n(n-1)}{8}$

The graph must be a tree