All Random Solved Random Open
Let $G$ be a regular graph with $2n$ vertices and degree $n+1$. Must $G$ have $\gg 2^{2n}$ subsets that are on a cycle?
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.