Problem Statement
Let $G$ be a regular graph with $2n$ vertices and degree $n+1$. Must $G$ have $\gg 2^{2n}$ subsets that are spanned by a cycle?
Categories:
Graph Theory
Progress
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.
Source: erdosproblems.com/622 | Last verified: January 15, 2026