A problem of Erdős and Faudree. Erdős writes 'it is easy to see' that there are at least $(\frac{1}{2}+o(1))2^{2n}$ sets that are not on a cycle.

If the regularity condition is replaced by minimum degree $n+1$ then the answer is no (consider $K_{n,n}$ with a spanning star in each part). Similarly this is false with degree $n$, as $K_{n,n}$ shows.

This has been resolved by Draganić, Keevash, and Müyesser [DKM25], who prove the asymptotically tight result that there are at least\[(\tfrac{1}{2}+o(1))2^{2n}\]subsets which are spanned by a cycle.

View the LaTeX source