Problem Statement
The cycle set of a graph $G$ on $n$ vertices is a set $A\subseteq \{3,\ldots,n\}$ such that there is a cycle in $G$ of length $\ell$ if and only if $\ell \in A$. Let $f(n)$ count the number of possible such $A$.
Prove that $f(n)=o(2^n)$.
Prove that $f(n)/2^{n/2}\to \infty$.
Prove that $f(n)=o(2^n)$.
Prove that $f(n)/2^{n/2}\to \infty$.
Categories:
Graph Theory Cycles
Progress
Conjectured by Erdős and Faudree, who showed that $2^{n/2}<f(n) \leq 2^{n-2}$. The first problem was solved by Verstraëte [Ve04], who proved\[f(n)\ll 2^{n-n^{1/10}}.\]This was improved by Nenadov [Ne25] to\[f(n) \ll 2^{n-n^{1/2-o(1)}}.\]One can also ask about the existence and value of $\lim f(n)^{1/n}$.Source: erdosproblems.com/84 | Last verified: January 13, 2026